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

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

In LeetCode 235: Lowest Common Ancestor of a Binary Search Tree, you’re given the root of a BST 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. A BST’s property (left < root < right) makes this simpler than in a general binary tree. This differs from linked list problems like LeetCode 234: Palindrome Linked List, focusing on tree navigation.

Problem Statement

• Input: Root of a BST and two nodes p and q.
• Output: The LCA node of p and q.
• Rules: Use BST properties; p and q exist in the tree.

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 = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
• Tree:

Copy code```
   6
  / \
 2   8
/ \ / \

0 4 7 9 / \ 3 5 ```

• Output: 6 (LCA of 2 and 8).

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

Understanding the Problem: Finding the LCA

To solve LeetCode 235: Lowest Common Ancestor of a Binary Search Tree in Python, we need to locate the node where the paths to p and q diverge. Unlike digit-counting tasks like LeetCode 233: Number of Digit One, this is about BST traversal. In a BST, if both nodes are less than the root, the LCA is in the left subtree; if both are greater, it’s in the right; if one is less and one is greater, the root is the LCA. We’ll explore two approaches: 1. Best Solution (BST Property-Based Traversal): O(h) time, O(1) space—leverages BST order. 2. Alternative Solution (Path Comparison): O(h) time, O(h) space—stores paths explicitly.

Let’s start with the best solution.

Best Solution: BST Property-Based Traversal

Why This Is the Best Solution

The BST property-based traversal is our top choice for LeetCode 235 because it uses the BST’s ordered nature to find the LCA in a single pass with no extra space beyond pointers. It’s efficient, intuitive for BSTs, and meets the problem’s constraints perfectly.

How It Works

• Start at the root.
• Compare p.val and q.val with the current node’s value:
• If both are less, move left.
• If both are greater, move right.
• If one is less and one is greater (or equal), the current node is the LCA.
• Continue until the split point is found.

Step-by-Step Example

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

• Tree Description:
• Root: 6
• Left: 2 (left: 0, right: 4; 4’s left: 3, right: 5)
• Right: 8 (left: 7, right: 9)
• Process:
• Node 6: p=2 < 6, q=8 > 6 → Split here, LCA = 6.
• Output: 6.

Example 2: p = 2, q = 4

• Process:
• Node 6: 2 < 6, 4 < 6 → Left to 2.
• Node 2: 2 = 2, 4 > 2 → Split at 2 (2 is ancestor of 4).
• Output: 2.

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: Start at root
        curr = root

        # Line 2: Traverse based on BST properties
        while curr:
            # Line 3: Both p and q less than current
            if p.val < curr.val and q.val < curr.val:
                curr = curr.left
            # Line 4: Both p and q greater than current
            elif p.val > curr.val and q.val > curr.val:
                curr = curr.right
            # Line 5: Split point found (one less, one greater, or equal)
            else:
                return curr

        # Line 6: Return LCA (won’t reach here due to problem constraints)
        return curr

• Time Complexity: O(h) – height of the tree, worst case O(n) for skewed tree.
• Space Complexity: O(1) – only uses a pointer.

Alternative Solution: Path Comparison Approach

Why an Alternative Approach?

The path comparison approach finds the LCA by recording paths from the root to p and q, then identifying the last common node. It’s a great alternative if you prefer explicit path tracking or want a method that’s easier to adapt to general binary trees, though it uses more space.

How It Works

• Traverse from root to p and q, storing paths in lists.
• Compare paths to find the last common node before divergence.

Step-by-Step Example

Example: p = 2, q = 8

• Path to p=2: [6, 2].
• Path to q=8: [6, 8].
• Compare: Common nodes = [6], last = 6.
• Output: 6.

Example: p = 3, q = 5

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

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 a node
        def find_path(node, target):
            path = []
            curr = node
            while curr:
                path.append(curr)
                if target.val < curr.val:
                    curr = curr.left
                elif target.val > curr.val:
                    curr = curr.right
                else:
                    break
            return path

        # 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(h) – two path traversals and comparison.
• Space Complexity: O(h) – stores paths.

Comparing the Two Solutions

• Best Solution (BST Property-Based Traversal):
• Pros: O(1) space, single pass, BST-optimized.
• Cons: Relies on BST properties.
• Alternative Solution (Path Comparison):
• Pros: Clear path logic, adaptable to non-BST.
• Cons: O(h) space.

The BST property-based method is our best for its efficiency and minimal space use.

Additional Examples and Edge Cases

Root as LCA

• Input: p = 0, q = 9
• Output: 6 (root).

Same Node

• Input: p = 4, q = 4
• Output: 4 (node itself).

Deep Nodes

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

Complexity Breakdown

• BST Property-Based:
• Time: O(h).
• Space: O(1).
• Path Comparison:
• Time: O(h).
• Space: O(h).

BST method excels in space efficiency.

Key Takeaways for Beginners

• LCA: Deepest common ancestor.
• BST Property: Guides traversal direction.
• Path Comparison: Tracks full routes.
• Python Tip: Pointers in trees—see [Python Basics](/python/basics).

Final Thoughts: Find Ancestors Like a Pro

LeetCode 235: Lowest Common Ancestor of a Binary Search Tree in Python is a delightful BST challenge. The BST property-based traversal offers a sleek, space-saving solution, while the path comparison approach provides clear insight. Want more tree adventures? Try LeetCode 236: Lowest Common Ancestor of a Binary Tree or LeetCode 104: Maximum Depth of Binary Tree. Ready to find LCAs? Head to Solve LeetCode 235 on LeetCode and trace those ancestors today!