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 Tthat has both p and q as descendants (where we allow a 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 are unique.

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.

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

Table of contents