# Mastering LeetCode: Solving the Lowest Common Ancestor of a Binary Tree Problem

## A step-by-step guide to finding the Lowest Common Ancestor in a binary tree using a recursive depth-first search approach.

## Solving the Lowest Common Ancestor of a Binary Tree on LeetCode

## Introduction

Finding the Lowest Common Ancestor (LCA) of two nodes in a binary tree is a classic problem often encountered in coding interviews and algorithm studies. Understanding how to solve this problem not only improves your problem-solving skills but also deepens your understanding of binary trees and recursive algorithms.

In this article, we will explore the problem, discuss a recursive approach to solving it, and implement the solution in Python.

### Understanding the Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes

`p`

and`q`

as the lowest node in`T`

that has both`p`

and`q`

as descendants (where we allowa node to be a descendant of itself).”

Example 1:`Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.`

Example 2:`Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.`

Example 3:`Input: root = [1,2], p = 1, q = 2 Output: 1`

Constraints:

The number of nodes in the tree is in the range

`[2, 10^5]`

.

`-10^9 <= Node.val <= 10^9`

All

`Node.val`

areunique.

`p != q`

`p`

and`q`

will exist in the tree.

## Recursive Depth-First Search Approach

To solve the problem, we can use a recursive depth-first search (DFS) approach. Here's the step-by-step strategy:

#### Base Case

The base case of the recursion checks if the current node is `None`

. If it is, we return `None`

, indicating that we have reached the end of a branch without finding `p`

or `q`

.

#### Match Case

If the current node is either `p`

or `q`

, we return the current node. This indicates that we have found one of the nodes we are looking for.

#### Recursive Search

We recursively search the left and right subtrees of the current node. If both left and right recursive calls return non-`None`

values, it means `p`

and `q`

are found in different subtrees, making the current node the LCA. If only one of the recursive calls returns a non-`None`

value, it means both `p`

and `q`

are located in the same subtree, and we return the non-`None`

result.

### Implementing the Solution in Python

Here’s the Python implementation of the recursive DFS approach:

```
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val: int = 0, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
self.val = val
self.left = left
self.right = right
class Solution:
def lowestCommonAncestor(self, root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
# Base case: if root is None, there's no LCA
if not root:
return None
# If the current node is either p or q, return it
if root == p or root == q:
return root
# Recursively search the left and right subtrees
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
# If both left and right are non-None, current node is the LCA
if left and right:
return root
# Otherwise, return non-None value from left or right
return left if left else right
```

### Explanation of the Code

**Base Case**: The check`if not root`

ensures we return`None`

if the current node is`None`

, indicating the end of a branch.**Match Case**: The check`if root == p or root == q`

returns the current node if it matches either`p`

or`q`

.**Recursive Search**: The recursive calls`left = self.lowestCommonAncestor(root.left, p, q)`

and`right = self.lowestCommonAncestor(root.right, p, q)`

search for`p`

and`q`

in the left and right subtrees.**Determine LCA**: The check`if left and right`

returns the current node as the LCA if both recursive calls are non-`None`

. Otherwise, it returns the non-`None`

result from the left or right subtree.

#### Edge Cases and Considerations

If

`p`

and`q`

are the same node, the algorithm correctly returns that node as the LCA.The solution assumes that both

`p`

and`q`

exist in the tree, as specified in the problem constraints.

## FAQ Section

#### What is the time complexity of the solution?

The time complexity of the solution is `O(N)`

, where `N`

is the number of nodes in the tree. This is because, in the worst case, the algorithm may need to traverse all the nodes in the tree.

#### Can this solution be adapted for a non-binary tree?

Yes, the solution can be adapted for a non-binary tree. However, the recursive search would need to be modified to iterate over all children of a node instead of just left and right children.

#### What are some common mistakes to avoid?

Not handling the case where one of the nodes is

`None`

.Assuming that the nodes

`p`

and`q`

are always different and exist in the tree without checking for it.

## Conclusion

Understanding and implementing the Lowest Common Ancestor problem in a binary tree is a valuable exercise in recursive problem-solving and binary tree traversal. By using a recursive depth-first search approach, we can efficiently find the LCA of two nodes, ensuring our solution is both correct and optimal.

Practice similar problems to further strengthen your grasp of these concepts.

### Related Articles

"Mastering LeetCode's "Lowest Common Ancestor in a BST": A Comprehensive Guide"

"Mastering the Backspace String Compare on LeetCode: A Comprehensive Guide"

"

**Mastering LeetCode: Counting the Number of Islands in a 2D Binary Grid****"**"Getting Started with Studying for Software Engineering Interviews Using LeetCode"