Can you find the lowest common ancestor of two nodes in a binary tree?

The Lowest Common Ancestor (LCA) in a binary tree for two nodes ‘n1‘ and ‘n2‘ is the deepest (lowest) node ‘v‘ that is an ancestor of both ‘n1‘ and ‘n2‘. If we designate each move from a node to its parent as a step, ‘v‘ would be the node for which the sum of the distances from ‘v‘ to ‘n1‘ and ‘n2‘ is the smallest. Here is the procedure to find the LCA in a binary tree:

First, we need to traverse the tree starting from the root node and search for nodes ‘n1‘ and ‘n2‘ (this can be completed using depth-first search, also known as DFS). For the DFS traversal, we can use a stack-based iterative method or a recursion-based approach.

Each time we visit a node during the DFS traversal, we record its parent. The parent can be stored in a dictionary.

Then, we create a set to contain all the ancestors for ‘n1‘ by exploring up from ‘n1‘ to root in the parent dictionary.

After that, we travel up from ‘n2‘ to the root. The first node that appears in the ‘n1‘’s ancestor set we have collected earlier will be the LCA. If ‘n2‘ reaches the root first, then ‘n2‘ will be the LCA.

Now let’s break the algorithm into pseudocode:

def findLCA(root, n1, n2):
    parent = {root: None}
    stack = [root]

    # Step 1: DFS until we find both the nodes n1 and n2
    while n1 not in parent or n2 not in parent:
        node = stack.pop()
        if node.left:
            parent[node.left] = node
            stack.append(node.left)
        if node.right:
            parent[node.right] = node
            stack.append(node.right)

    # Step 2: Create a set of n1's ancestors
    ancestors = set()
    while n1:
        ancestors.add(n1)
        n1 = parent[n1]

    # Step 3: The first ancestor of n2 which appears in
    # n1's ancestor set() is their lowest common ancestor
    while n2 not in ancestors:
        n2 = parent[n2]

    return n2

Note: An important thing to mention about this code is that for it to work as is, it assumes that nodes ‘n1‘ and ‘n2‘ are guaranteed to be in the tree. If that’s not the case, the code should be modified to handle the scenario when ‘n1‘ and/or ‘n2‘ are not in the tree. Also, since binary trees do not have a parent pointer, this code creates an additional data structure, a map to track parent pointers. If you have a binary tree with parent pointer or if you can modify the node structure to include a parent pointer, you can take advantage of this simplification.

This algorithm runs in ‘O(N)‘ time where ‘N‘ is the number of nodes in the binary tree (due to the DFS) and requires ‘O(N)‘ space to keep track of parent pointers.