Lowest Common Ancestor

Search for both nodes at once. Recurse into the left and right subtrees. If one target is found in each subtree, the current node is their lowest common ancestor. If both targets are in the same subtree, that subtree's answer bubbles up, and if the current node is one of the targets, it is the answer by definition.

The definition matters here. The lowest common ancestor is the deepest node that has both targets as descendants, and a node counts as its own descendant. That is why the base case returns the current node when it matches either target.

The mechanism is that the recursive call returns either the answer or nothing, and the current node combines the two results. When both sides produce a node, the current node is the first point where the two paths diverge, which is exactly the definition. When only one side produces a node, that node is the answer and it is passed up unchanged.

The trade-off to name is that this works on any binary tree, including one that is not a search tree, and it costs linear time with linear space for the recursion stack. On a search tree you can do better, because the ordering tells you which side each target lives in, so a single descent finds the answer in time proportional to the height. For a tree with very many nodes and frequent queries, precomputing the answer for every pair of nodes is another option, at the cost of quadratic space.

Recurse into both subtrees and combine the results. If both sides find something, the current node is the answer; otherwise pass up whichever side found something.

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


def lowest_common_ancestor(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left is not None and right is not None:
        return root
    return left if left is not None else right


tree = TreeNode(3,
                TreeNode(5),
                TreeNode(1, TreeNode(6), TreeNode(2)))
print(lowest_common_ancestor(tree, tree.left, tree.right).value)

The output is 3. The two targets are the node with value five, which is the left child of the root, and the node with value one, which is the right child. Their paths diverge at the root, so the root is the answer.

The mechanism is the combination step. Each recursive call returns the answer found in its subtree, or None if neither target is there. If the current node itself is one of the targets, it is returned immediately, which is the case where one target is an ancestor of the other. If both children return a node, the targets were found on opposite sides and the current node is where their paths meet.

The trade-off to name is identity versus value. The code compares node objects rather than values, which is the correct choice when a tree may contain duplicate values, and it assumes both targets actually exist in the tree. If they might not, you need to return None explicitly rather than the root, and a separate pass to check that both are present. The complexity is linear in the number of nodes with stack space proportional to the height, which is worse than the search tree version that follows in the next answer.

The same recursive algorithm handles it, because the base case returns the current node when it matches one of the targets. If one target is an ancestor of the other, the recursion stops as soon as it reaches that ancestor and returns it directly.

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


def lowest_common_ancestor(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left is not None and right is not None:
        return root
    return left if left is not None else right


tree = TreeNode(3, TreeNode(5, TreeNode(6)), TreeNode(1))
print(lowest_common_ancestor(tree, tree.left, tree.left.left).value)

The output is 5. The node with value six is a descendant of the node with value five, so the deepest node that has both as descendants is the node with value five itself.

The mechanism is the order of the base case checks. The function returns the current node when it is either of the targets, before it ever recurses, so the recursion unwinds immediately with that node and the ancestor case never reaches the combination step.

The trade-off to name is that this behaviour is a consequence of the definition, and it is worth checking which definition your interviewer is using. Some versions of the problem state that a node is not its own descendant, in which case the ancestor case has no solution and you would need to return None or handle it separately. Saying that you are treating a node as its own descendant, and that this matches the standard definition, removes the ambiguity. The other point is that this recursive form works on any binary tree, while on a search tree the same question has a much faster solution because the ordering tells you where to look.