1650. Lowest Common Ancestor of a Binary Tree III

Difficulty: Medium
Category: Tree, Binary Tree, LCA

Problem Statement

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

Each node has a reference to its parent node. The definition of LCA is: “The lowest common ancestor of two nodes p and q in a tree is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Examples

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.

Approach

This is a variation of the Lowest Common Ancestor (LCA) problem where each node has a reference to its parent. The key insight is to use the two-pointer technique similar to finding the intersection of two linked lists.

Algorithm:

  1. Start from both nodes p and q
  2. Traverse upward using parent pointers
  3. When one pointer reaches null, redirect it to the other node
  4. Continue until both pointers meet at the LCA
  5. Return the meeting point

Key Insight:

This approach ensures both pointers travel the same total distance, making them meet at the LCA.

Solution

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        a, b = p, q
        while a != b:
            a = q if a is None else a.parent
            b = p if b is None else b.parent
        return a

<｜tool▁calls▁begin｜><｜tool▁call▁begin｜> read_file


## Explanation

### Step-by-Step Process:

1. **Initialize pointers:** `a = p`, `b = q`
2. **Traverse upward:** While `a != b`:
   - If `a` is null, redirect to `q`; otherwise move to parent
   - If `b` is null, redirect to `p`; otherwise move to parent
3. **Return meeting point:** When `a == b`, return the LCA

### Why This Works:

**Distance Equalization:**
- **Path from p to root:** Let's say it has length `m`
- **Path from q to root:** Let's say it has length `n`
- **Total distance traveled by each pointer:** `m + n`
- **Meeting point:** Both pointers meet at the LCA

**Example Walkthrough:**
For a tree where `p` is at depth 2 and `q` is at depth 3:

- **Pointer a (from p):** p → parent → root → q → parent → LCA
- **Pointer b (from q):** q → parent → parent → root → p → parent → LCA
- **Both travel same distance:** 5 steps each
- **Meet at LCA:** After equal distance traveled

### Visual Example:

    Root
   /    \
  A      B
 / \    / \
C   D  E   F    /   G ```

If p = G and q = F:

  • Path from G to root: G → C → A → Root (3 steps)
  • Path from F to root: F → B → Root (2 steps)
  • Pointer a: G → C → A → Root → F → B → Root (6 steps)
  • Pointer b: F → B → Root → G → C → A → Root (6 steps)
  • Meet at Root: LCA = Root

Complexity Analysis

Time Complexity: O(h) where h is the height of the tree

  • In worst case, both nodes are at maximum depth
  • Each pointer travels at most 2h steps (h up + h down)

Space Complexity: O(1)

  • Only using two pointers, no additional data structures

Key Insights

  1. Two-Pointer Technique: Similar to finding linked list intersection
  2. Distance Equalization: Both pointers travel same total distance
  3. Parent Pointer Utilization: Leverages the parent reference efficiently
  4. No Extra Space: Constant space solution
  5. Elegant Logic: Simple but powerful algorithm

Alternative Approaches

Approach 1: Path Collection

def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
    path = set()
    
    # Collect path from p to root
    curr = p
    while curr:
        path.add(curr)
        curr = curr.parent
    
    # Find first common node in path from q to root
    curr = q
    while curr:
        if curr in path:
            return curr
        curr = curr.parent
    
    return None

Approach 2: Depth Calculation

def getDepth(self, node: 'Node') -> int:
    depth = 0
    while node:
        depth += 1
        node = node.parent
    return depth

def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
    depthP = self.getDepth(p)
    depthQ = self.getDepth(q)
    
    # Move deeper node up to same level
    while depthP > depthQ:
        p = p.parent
        depthP -= 1
    while depthQ > depthP:
        q = q.parent
        depthQ -= 1
    
    # Move both up until they meet
    while p != q:
        p = p.parent
        q = q.parent
    
    return p

Comparison of Approaches

Approach Time Space Elegance
Two-Pointer O(h) O(1) ⭐⭐⭐⭐⭐
Path Collection O(h) O(h) ⭐⭐⭐
Depth Calculation O(h) O(1) ⭐⭐⭐⭐

The two-pointer approach is optimal because:

  • Constant Space: No additional data structures
  • Elegant Logic: Simple and intuitive
  • Efficient: Single pass through the tree
  • Clean Code: Minimal implementation

Key Concepts

  1. Lowest Common Ancestor: Deepest node that has both nodes as descendants
  2. Parent Pointer: Each node knows its parent (unlike standard binary tree)
  3. Two-Pointer Technique: Classic algorithm pattern for finding intersections
  4. Distance Equalization: Mathematical insight that makes the algorithm work
  5. Tree Traversal: Upward traversal using parent pointers

This problem demonstrates the power of the two-pointer technique and shows how mathematical insights can lead to elegant solutions in tree problems.