Lowest Common Ancestor of a Binary Tree III

Problem#

Each node has a parent pointer. Given two nodes p and q, return their lowest common ancestor.

Examples#

For a balanced tree with p = node(5) and q = node(1), the LCA might be the root.

Constraints#

All values unique; both nodes exist in the tree.

Hints#

Hint 1

Walking from each node up toward the root produces two “linked lists” that must meet at the LCA.

Hint 2

After one pointer hits null, restart it at the other node — the lengths cancel.

Approach#

Each ancestor path is a linked list ending at root. Two paths from different nodes share a suffix starting at the LCA. The classic “intersection of two linked lists” pointer trick (swap pointer to the other start when reaching null) makes them meet exactly at the intersection point in O(h₁ + h₂) steps.

Solution#

class Solution {
public:
    Node* lowestCommonAncestor(Node* p, Node* q) {
        Node *a = p, *b = q;
        while (a != b) {
            a = a ? a->parent : q;
            b = b ? b->parent : p;
        }
        return a;
    }
};

type Node struct {
    Val    int
    Left   *Node
    Right  *Node
    Parent *Node
}

func lowestCommonAncestor(p, q *Node) *Node {
    a, b := p, q
    for a != b {
        if a != nil {
            a = a.Parent
        } else {
            a = q
        }
        if b != nil {
            b = b.Parent
        } else {
            b = p
        }
    }
    return a
}

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

function lowestCommonAncestor(p, q) {
    let a = p, b = q;
    while (a !== b) {
        a = a ? a.parent : q;
        b = b ? b.parent : p;
    }
    return a;
}

class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        Node a = p, b = q;
        while (a != b) {
            a = (a != null) ? a.parent : q;
            b = (b != null) ? b.parent : p;
        }
        return a;
    }
}

interface Node {
    val: number;
    left: Node | null;
    right: Node | null;
    parent: Node | null;
}

function lowestCommonAncestor(p: Node | null, q: Node | null): Node | null {
    let a = p, b = q;
    while (a !== b) {
        a = a ? a.parent : q;
        b = b ? b.parent : p;
    }
    return a;
}

Editorial#

Imagine each node’s ancestor chain as a linked list. Two such lists must converge at the LCA (and from there on are identical). The pointer-swap trick aligns their effective starting positions: pointer a walks length len(p) + len(q) before meeting b, which walks the same total. They land on the intersection node simultaneously. If they never share an ancestor (disjoint trees), both pointers reach null at the same step and the loop exits with a == b == nullptr.

Complexity#

Time: O(h₁ + h₂) — bounded by tree height.
Space: O(1).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#