Java Coding Test Course, Finding the Lowest Common Ancestor 2

Problem Description

The problem of finding the Lowest Common Ancestor (LCA) of two nodes in a given binary tree is an important topic in various algorithm problem solving. This problem particularly requires understanding of tree structures and recursive thinking. In this article, we will take a deep dive into how to find the Lowest Common Ancestor.

Problem Definition

Given a root node of a binary tree and two nodes A and B, you need to solve the problem of finding the Lowest Common Ancestor of A and B. The Lowest Common Ancestor is defined as the deepest (lowest) node that satisfies the following conditions:

  • It must include all ancestors of nodes A and B.
  • The node LCA must exist within the subtree where A and B are located.

Constraints

The given binary tree has the following constraints:

  • The number of nodes is between 1 and 10^4.
  • Each node has a unique value.
  • Both A and B must be nodes that exist in the tree.

Problem Solving Strategy

1. Understanding Tree Structure

A tree is a hierarchical data structure composed of nodes and edges. In the case of a binary tree, each node can have at most two children. To find the Lowest Common Ancestor based on the depth of the tree, we need to acquire the following resources.

2. Algorithm Selection

We can use DFS (Depth-First Search) as the candidate algorithm. This approach involves the following steps:

  1. Start from the root node and explore the left and right subtrees.
  2. If both nodes A and B exist in their respective subtrees, the current node becomes the LCA.
  3. If either A or B exists in only one subtree, return that node.
  4. If neither exists, return null.

Python Implementation


# Definition of a binary tree node
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Finding LCA
def lowestCommonAncestor(root, p, q):
    if root is None:
        return None
    
    if root == p or root == q:
        return root
    
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    if left and right:
        return root
    return left if left else right

Implementation Explanation

1. TreeNode Class

First, we define the TreeNode class to store the value of each node. Each node references its left (left) and right (right) child nodes, in addition to its value (val).

2. lowestCommonAncestor Function

Starting from the given root node, we recursively call the function to find the LCA of the two nodes A and B. The base cases are when the node is null or the root is A or B, in which case we return the current node.

Since we are looking for the LCA in each subtree, if both values returned from the left and right subtrees exist, the current node is the LCA.

3. Problem Solving

Now, we can use this algorithm to find the LCA for the two nodes A and B in the given binary tree. The time complexity of the algorithm is O(N), where N is the number of nodes.

Performance Validation

We can test this algorithm with various inputs to validate its performance. For example, we can consider the following binary tree as input. 


    # Example tree creation
    root = TreeNode(3)
    root.left = TreeNode(5)
    root.right = TreeNode(1)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(2)
    root.right.left = TreeNode(0)
    root.right.right = TreeNode(8)
    root.left.right.left = TreeNode(7)
    root.left.right.right = TreeNode(4)

    p = root.left         # Node with value 5
    q = root.left.right.right  # Node with value 4

    ancestor = lowestCommonAncestor(root, p, q)
    print(ancestor.val)  # Expected output: 5

Conclusion

In this lecture, we thoroughly covered finding the Lowest Common Ancestor, which is one of the important concepts in Java coding tests. This algorithm can be utilized in various situations and is very helpful for understanding tree structures. I hope the problem-solving process and algorithm analysis will assist you in preparing for coding tests.

If you have any additional questions, please leave them in the comments. Thank you!