Python Coding Test Course, Finding the Lowest Common Ancestor 1

Hello, everyone! Today, we will learn about one of the common problems in coding tests using Python, which is “Finding the Lowest Common Ancestor.” In this tutorial, we will explain the algorithm to find the ‘Lowest Common Ancestor (LCA)’ in detail, along with related example problems and their solutions.

1. Problem Definition

This problem involves finding the lowest common ancestor of two nodes A and B in a given binary tree. The lowest common ancestor refers to the deepest node that has both nodes as children. For example, let’s assume we have the following binary tree.

In the above tree, the lowest common ancestor of node 5 and node 1 is node 3. However, the lowest common ancestor of node 5 and node 4 is node 5.

2. Problem Requirements

Input: The root node of the binary tree and two nodes A, B
Output: Return the lowest common ancestor node of A and B

3. Algorithm Approach

There are several approaches to find the lowest common ancestor, but the simplest method uses DFS (Depth First Search). By using the DFS algorithm, we can visit each node to search for A and B and track their common ancestor.

3.1 DFS Search Method

While exploring the binary tree using DFS, check if the current node matches either of the two nodes A and B. If it matches, return that node. If not, search for A and B in the two subtrees. The next step is to combine the results from these two subtrees to find the lowest common ancestor.

3.2 Implementation

Now, let’s write the code to solve the problem.


class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def lowest_common_ancestor(root, node1, node2):
    if root is None:
        return None

    # base case: if the current root is one of the nodes
    if root == node1 or root == node2:
        return root

    # look for node1 and node2 in the left and right subtrees
    left_lca = lowest_common_ancestor(root.left, node1, node2)
    right_lca = lowest_common_ancestor(root.right, node1, node2)

    # If both left_lca and right_lca are not None, it means
    # one node is present in one subtree and the other is present in the other subtree
    if left_lca and right_lca:
        return root

    # Otherwise return the non-null value
    return left_lca if left_lca is not None else right_lca

4. Code Explanation

First, we define the TreeNode class to represent each node of the binary tree. This class holds the value of each node and its left and right children. Next, we define the lowest_common_ancestor function to find the lowest common ancestor of two nodes, node1 and node2, starting from the given root node.

4.1 Base Condition

If the root node is None, we return None. If the current root is equal to node1 or node2, we return that node.

4.2 Recursive Search

Next, we recursively look for LCA in both the left and right subtrees. If a node is found in both subtrees, the current node is the lowest common ancestor. Otherwise, we return the found node.

5. Test Cases

To test the function, let’s set up the following tree.

            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)


# Test case 1: Finding LCA of 5 and 1
lca = lowest_common_ancestor(root, root.left, root.right)  # should return TreeNode(3)

# Test case 2: Finding LCA of 5 and 4
lca = lowest_common_ancestor(root, root.left, root.left.right.right)  # should return TreeNode(5)

6. Conclusion

In this tutorial, we learned how to find the lowest common ancestor in a binary tree using Python. We explored the process of solving the problem using the DFS algorithm, which enhanced our understanding of binary trees. In the next tutorial, we will cover more complex binary tree problems, so please stay tuned!

Through this article, I hope you have gained an understanding of the LCA problem and the ability to solve it. Thank you!