Lowest Common Ancestor of a Binary Tree

Question

Given a binary tree and two nodes, find their lowest common ancestor. Meta frequently asks tree traversal problems to evaluate recursive thinking and edge case handling.

Codemia · Accepted Answer

To find the Lowest Common Ancestor (LCA) of two nodes in a binary tree, we can utilize a recursive approach that leverages the properties of a binary tree. The LCA of two nodes is defined as the deepest node that is an ancestor to both nodes. This problem can be effectively solved using a depth-first search (DFS) strategy, which allows us to explore each branch of the tree until we find the nodes in question. The key pattern here is that we need to traverse the tree and check the conditions of the nodes recursively.

1. Start from the root of the binary tree. 
2. If the current node is NULL, return NULL (base case). 
3. If the current node matches either of the two nodes (let's call them `p` and `q`), return the current node. 
4. Recursively call the function on the left and right children of the current node. 
5. After the recursive calls, check if both left and right recursive calls returned non-NULL values. If they did, it means `p` and `q` are found in different subtrees, and the current node is their LCA. 
6. If only one of the children returned a non-NULL value, return that child (it could be either `p` or `q`).

**Example**: 
For the tree: 
```
       3
      / \
     5   1
    / \ / \
   6  2 0  8
     / \
    7   4
```
If `p` = 5 and `q` = 1, the algorithm will return 3. If `p` = 5 and `q` = 4, it will return 5.

Here is a Python implementation of the above approach:
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    if not root:
        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
```

The time complexity of this solution is O(N), where N is the number of nodes in the binary tree. In the worst case, we may have to visit every node once, especially in a skewed tree. The space complexity is O(H), where H is the height of the tree, due to the recursion stack. In the worst case (for a skewed tree), H can be equal to N, while in a balanced tree, H would be log(N).

1. **Both nodes are the same**: If `p` and `q` are the same node, the LCA should return that node itself. 
2. **One node is the ancestor of the other**: If `p` is an ancestor of `q`, the function should return `p`. 
3. **Null root**: If the tree is empty (root is NULL), the function should handle this gracefully and return NULL. 
4. **Nodes do not exist in the tree**: If either `p` or `q` do not exist in the tree, the function should still return the LCA of the existing node, if applicable.

Lowest Common Ancestor of a Binary Tree

Meta

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Meta Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string