Learn to solve the Lowest Common Ancestor (LCA) problem for binary trees, a must-know coding challenge for Amazon SDE interviews. Explore the solution with time/space complexity analysis.

Blog

Binary trees are widely used data structures, and questions related to them are popular in coding interviews.

We'll start with a simple example to understand the problem better, and then we'll explore a recursive approach to solve it.

I'll provide the solution in Python, but feel free to adapt it to your preferred programming language.

Given a binary tree and two nodes in the tree, find the lowest common ancestor (LCA) of the two nodes. The LCA is the deepest node in the tree that has both the given nodes as descendants.

**For example, consider the following binary tree:**

```
3
/ \
5 1
/ \ \
6 2 0
/ \
7 4
```

If the two nodes are 5 and 1, the LCA is 3.

If the two nodes are 6 and 4, the LCA is 5.

We can solve this problem using a recursive approach.

The idea is to traverse the tree and check if the current node is equal to one of the given nodes or if the LCA lies in the left or right subtree.

**Here's the implementation in Python:**

```
Class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def lowestCommonAncestor(root, p, q):
# Base case: If the root is None or matches either p or q, return the root
if root is None or root == p or root == q:
return root
# Recursively search for p and q in the left and right subtrees
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
# If both p and q are found in different subtrees, the current node is the LCA
if left and right:
return root
# If either p or q is found, return the non-null node
return left if left else right
```

- The base case handles when the root is
**None**(empty tree) or when the root matches either**p**or**q**. In these cases, we return the root itself. - We recursively search for
**p**and**q**in the left and right subtrees by calling**lowestCommonAncestor**on the left and right children of the current node. - If both
**left**and**right**returns non-null values, it means that**p**and**q**are present in different subtrees, and the current node is the LCA. We return the current node (**root**) in this case. - If either
**left**or**right**returns a non-null value, it means that either**p**or**q**is found in that subtree. We return the non-null value, which will propagate up the recursion stack until we find the LCA. - If both
**left**and**right**are**None**, it means that neither**p**nor**q**is present in the current subtree, and we return**None**.

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 might need to visit all nodes to find the LCA.

The space complexity is O(N) in the worst case (skewed tree), which may arise due to recursive calls on the call stack.

However, for a balanced tree, the space complexity is O(log N) due to the limited depth of recursive calls.

This solution assumes that both `p`

and `q`

are present in the binary tree. If either

or **p**

is not present in the tree, the function will return **q**

.**None**

That's it, folks!

I hope this in-depth look at the Lowest Common Ancestor problem for binary trees has given you a solid understanding of the problem and how to approach it.

If you're preparing for software engineering interviews or want to level up your problem-solving skills, please connect with me.

As an SDE at Amazon and a mentor, I'm always happy to share more insight into coding interview prep, discuss more such questions, and provide guidance on your coding journey.

Remember, consistent effort is the key to cracking those challenging coding interviews. Best of luck!