Lowest Common Ancestor of a Binary Tree III

1650.Lowest Common Ancestor of a Binary Tree III

Tree

Two Pointers

Problem Statement:

Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA). Each node has a parent pointer but no root reference is given. An ancestor of a node is a node that is on the path from that node to the tree root.

Intuition:

This problem is identical to finding intersection in linked lists because: - Following parent pointers is like traversing a linked list - Two paths to root will intersect at LCA - Can use same trick of switching pointers when reaching null - Pointers will meet at LCA after traveling equal distances

Example:

Input:

p = [3,5,1,6,2,0,8], q = [5]

→

Output:

Node 5

Java Solution:

// Same approach as finding intersection in linked lists - IDENTICAL TO LC160 
// Both pointers will meet at LCA after switching paths
public Node lowestCommonAncestor(Node p, Node q) {
    Node a = p, b = q;
    
    // Continue until pointers meet
    while (a != b) {
        // Switch to other node's path when reaching root
        a = a == null ? q : a.parent;
        b = b == null ? p : b.parent;    
    }
    
    // Pointers will meet at LCA
    return a;
}

Python Solution:

def lowestCommonAncestor(self, p: Node, q: Node) -> Node:
    # Initialize pointers to start nodes
    a, b = p, q
    
    # Loop until pointers meet
    while a != b:
        # Switch paths at root
        a = q if a is None else a.parent
        b = p if b is None else b.parent
        
    return a

C++ Solution:

class Solution {
public:
    Node* lowestCommonAncestor(Node* p, Node* q) {
        Node *a = p, *b = q;
        
        // Continue until pointers align
        while(a != b) {
            // Switch paths at null
            a = a ? a->parent : q;
            b = b ? b->parent : p;
        }
        
        return a;
    }
};