Lowest Common Ancestor of a Binary Tree – LeetCode75 Python Solution Explained

The Lowest Common Ancestor of a Binary Tree problem (LeetCode75) is a widely asked question in coding interviews. It tests your understanding of tree traversal, recursion and path comparison.

In this blog, we’ll explain the problem, provide a Python solution, a step-by-step explanation with code snippets, analyze complexities and discuss practical applications.

Problem Statement

Given a binary tree and two nodes p and q, find their lowest common ancestor (LCA).

Definition:
The LCA of two nodes p and q is the lowest node in the tree that has both p and q as descendants (where a node can 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: Node 5 is the ancestor of node 4, so LCA is 5.

Understanding the Problem

Key points:

• The LCA is the deepest node that has both p and q as descendants.
• There are multiple approaches:
  1. Path comparison – store paths from root to p and q, then find the last common node.
  2. Recursive DFS – traverse the tree and return the node when both children contain p or q.
• We’ll focus on the path comparison method in this example.

Complete Python Solution

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # Helper function to find path from root to target node
        def findPath(node, target, path):
            if not node:
                return None
            path.append(node)
            if node == target:
                return path
            left_path = findPath(node.left, target, path.copy())
            right_path = findPath(node.right, target, path.copy())
            return left_path or right_path
        
        path_p = findPath(root, p, [])
        path_q = findPath(root, q, [])

        lca = None

        # Compare paths to find last common node
        for node_p, node_q in zip(path_p, path_q):
            if node_p == node_q:
                lca = node_p
            else:
                break
                
        return lca

Step-by-Step Explanation

Step 1: Find Path from Root to Node

Use a recursive helper function findPath to find the path from root to the target node.

def findPath(node, target, path):
    if not node:
        return None
    path.append(node)
    if node == target:
        return path

Step 2: Recurse on Left and Right Subtrees

Check left and right subtrees and return the path if the node is found:

left_path = findPath(node.left, target, path.copy())
right_path = findPath(node.right, target, path.copy())
return left_path or right_path

Step 3: Compare Paths

Once paths to p and q are found, iterate through both paths and find the last common node:

for node_p, node_q in zip(path_p, path_q):
    if node_p == node_q:
        lca = node_p
    else:
        break

This node is the Lowest Common Ancestor.

Step 4: Return LCA

return lca

Time and Space Complexity

• Time Complexity: O(n) – Each node may be visited during path search.
• Space Complexity: O(n) – Storing paths and recursion stack.

Edge Cases

1. Tree with only root node – LCA is the root itself.
2. Nodes are the same – LCA is the node itself.
3. Nodes not present in tree – Return None.

Real-World Applications

• File Systems: Finding common parent directory of two files.
• Organizational Hierarchy: Lowest manager common to two employees.
• Genealogy Trees: Identifying common ancestor in family trees.
• Network Routing: Finding common node in hierarchical network structures.

Conclusion

The Lowest Common Ancestor of a Binary Tree is a fundamental problem in tree algorithms. Path comparison is intuitive and easy to implement. Recursive DFS methods can optimize for larger trees.

Understanding LCA helps in binary tree algorithms, hierarchical structures and interview preparation.

Related Reads

• Longest ZigZag Path in a Binary Tree – LeetCode75 Python Solution Explained
• Path Sum III – LeetCode75 Python Solution Explained
• Count Good Nodes in a Binary Tree – LeetCode75 Python Solution Explained
• Maximum Depth of a Binary Tree – LeetCode75 Python Solution Explained
• Maximum Twin Sum of a Linked List – LeetCode75 Python Solution Explained

References

1. LeetCode 236 – Lowest Common Ancestor of a Binary Tree
2. Programiz – Binary Tree in Python
3. Wikipedia – Binary Tree