Find the Lowest Common Ancestor in a Binary Tree

Question

The candidate is asked to find the lowest common ancestor (LCA) of two nodes in a binary tree.

Codemia · Accepted Answer

To find the lowest common ancestor of two nodes in a binary tree, we can use a recursive approach. The idea is to traverse the tree starting from the root and check if the current node is one of the nodes we are looking for. If we find either node, we return it; otherwise, we check both the left and right subtrees.

Here's a Python implementation of the algorithm:

```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
```

This function checks if the current node is `None`, if it matches either of the nodes `p` or `q`, and recursively searches in the left and right subtrees.

The time complexity of this algorithm is O(N), where N is the number of nodes in the binary tree, since we may need to visit every node in the worst case. The space complexity is O(H), where H is the height of the tree, due to the recursion stack.

This approach is straightforward and works well for binary trees. However, if we were to optimize for space complexity, we could consider an iterative approach using parent pointers or a stack, but that would complicate the solution.

Find the Lowest Common Ancestor in a Binary Tree

Amazon

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Amazon 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