LeetCode 236: Lowest Common Ancestor of a Binary Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 236: Lowest Common Ancestor of a Binary Tree?

In LeetCode 236: Lowest Common Ancestor of a Binary Tree, you’re given the root of a binary tree and two nodes p and q, and your task is to return their lowest common ancestor—the deepest node that is an ancestor of both. Unlike BSTs, this tree has no ordering, making it a broader challenge than LeetCode 235.

Problem Statement

• Input: Root of a binary tree and two nodes p and q.
• Output: The LCA node of p and q.
• Rules: p and q exist in the tree; all values are unique.

Constraints

• Number of nodes: 2 to 10^5.
• Node values: -10^9 to 10^9, unique.
• p ≠ q, and both are in the tree.

Examples

• Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
• Tree:

Copy code```
   3
  / \
 5   1
/ \ / \

6 2 0 8 / \ 7 4 ```

• Output: 3 (LCA of 5 and 1).

• Output: 5 (LCA of 5 and 4, as 5 is an ancestor of 4).

Understanding the Problem: Finding the LCA

To solve LeetCode 236: Lowest Common Ancestor of a Binary Tree in Python, we need to locate the node where paths to p and q converge. This isn’t about palindrome checks like LeetCode 234: Palindrome Linked List—it’s about tree traversal. Without BST ordering, we can’t rely on value comparisons alone; we must search both subtrees. We’ll explore two approaches: 1. Best Solution (Bottom-Up Traversal): O(n) time, O(h) space—elegant and efficient. 2. Alternative Solution (Path Comparison): O(n) time, O(h) space—explicit path tracking.

Let’s start with the best solution.

Best Solution: Bottom-Up Traversal Approach

Why This Is the Best Solution

The bottom-up traversal approach is our top choice for LeetCode 236 because it efficiently identifies the LCA in a single pass by propagating information from leaves to root, using minimal extra space. It’s intuitive once understood and optimal for binary trees, making it a standout solution.

How It Works

• Traverse the tree bottom-up:
• Check left and right subtrees for p or q.
• If a node finds p or q in one subtree and the other in another (or itself is one), it’s the LCA.
• If only one is found, pass it up; if neither, return None.
• The first node encountering both is the LCA.

Step-by-Step Example

Example 1: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

• Tree Description:
• Root: 3
• Left: 5 (left: 6, right: 2; 2’s left: 7, right: 4)
• Right: 1 (left: 0, right: 8)
• Process:
• Node 5: Left (6) = None, Right (2) = None, Self = 5 → Return 5.
• Node 1: Left (0) = None, Right (8) = None, Self = 1 → Return 1.
• Node 3: Left (5) = 5, Right (1) = 1 → LCA = 3 (both found).
• Output: 3.

Example 2: p = 5, q = 4

• Process:
• Node 7: None.
• Node 4: Self = 4 → Return 4.
• Node 2: Left (7) = None, Right (4) = 4 → Return 4.
• Node 5: Left (6) = None, Right (2) = 4, Self = 5 → LCA = 5.
• Output: 5.

Code with Detailed Line-by-Line Explanation

Here’s the Python implementation:

Copy code# 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':
        # Line 1: Base case - empty node
        if not root:
            return None

        # Line 2: Check left subtree
        left = self.lowestCommonAncestor(root.left, p, q)

        # Line 3: Check right subtree
        right = self.lowestCommonAncestor(root.right, p, q)

        # Line 4: Determine LCA
        if left and right:
            return root  # p and q split across subtrees
        if root == p or root == q:
            return root  # Current node is p or q
        return left if left else right  # Pass up found node

        # Note: Execution starts from root call in problem context

• Time Complexity: O(n) – visits each node once.
• Space Complexity: O(h) – call stack depth, h is tree height.

Alternative Solution: Path Comparison Approach

Why an Alternative Approach?

The path comparison approach explicitly tracks paths from root to p and q, then finds the last common node. It’s a great alternative if you prefer a visual, step-by-step method or need adaptability for other tree problems, though it uses more space.

How It Works

• Find paths from root to p and q using traversal.
• Compare paths to identify the last shared node before divergence.

Step-by-Step Example

Example: p = 5, q = 1

• Path to p=5: [3, 5].
• Path to q=1: [3, 1].
• Compare: Common = [3], LCA = 3.
• Output: 3.

Example: p = 7, q = 4

• Path to p=7: [3, 5, 2, 7].
• Path to q=4: [3, 5, 2, 4].
• Compare: Common = [3, 5, 2], LCA = 2.
• Output: 2.

Code for Path Comparison Approach

Copy codeclass 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':
        # Line 1: Find path to target node
        def find_path(node, target, path=[]):
            if not node:
                return None
            path.append(node)
            if node == target:
                return path[:]
            left = find_path(node.left, target, path)
            if left:
                return left
            right = find_path(node.right, target, path)
            if right:
                return right
            path.pop()
            return None

        # Line 2: Get paths to p and q
        path_p = find_path(root, p)
        path_q = find_path(root, q)

        # Line 3: Find last common node
        lca = None
        for i in range(min(len(path_p), len(path_q))):
            if path_p[i] != path_q[i]:
                break
            lca = path_p[i]

        # Line 4: Return LCA
        return lca

• Time Complexity: O(n) – two traversals and comparison.
• Space Complexity: O(h) – stores paths.

Comparing the Two Solutions

• Best Solution (Bottom-Up Traversal):
• Pros: O(n) time, elegant, minimal space usage.
• Cons: Requires understanding bottom-up logic.
• Alternative Solution (Path Comparison):
• Pros: Clear path tracking, adaptable.
• Cons: Extra space for paths.

The bottom-up method is our best for its efficiency and elegance.

Additional Examples and Edge Cases

Root as LCA

• Input: p = 5, q = 1
• Output: 3.

Same Node

• Input: p = 2, q = 2
• Output: 2.

Deep Nodes

• Input: p = 7, q = 4
• Output: 2.

Complexity Breakdown

• Bottom-Up Traversal:
• Time: O(n).
• Space: O(h).
• Path Comparison:
• Time: O(n).
• Space: O(h).

Both are time-optimal; bottom-up is more space-efficient in practice.

Key Takeaways for Beginners

• LCA: Deepest common ancestor.
• Bottom-Up: Propagates findings upward.
• Path Comparison: Tracks full routes.
• Python Tip: Tree traversal—see [Python Basics](/python/basics).

Final Thoughts: Trace Ancestors Like a Pro

LeetCode 236: Lowest Common Ancestor of a Binary Tree in Python is a captivating tree challenge. The bottom-up traversal solution offers a sleek, efficient path, while the path comparison approach provides clear visibility. Want more tree fun? Try LeetCode 235: Lowest Common Ancestor of a BST or LeetCode 104: Maximum Depth of Binary Tree. Ready to find LCAs? Head to Solve LeetCode 236 on LeetCode and uncover that ancestor today!