LeetCode 1650 - Lowest Common Ancestor of a Binary Tree III

This problem asks us to find the lowest common ancestor, usually abbreviated as LCA, of two nodes in a binary tree. Unli

leetcodemediumhash-tabletwo-pointerstreebinary-tree

LeetCode Problem 1650

Difficulty: 🟡 Medium
Topics: Hash Table, Two Pointers, Tree, Binary Tree

Solution

Problem Understanding

This problem asks us to find the lowest common ancestor, usually abbreviated as LCA, of two nodes in a binary tree. Unlike the classic version of the problem, every node contains a direct pointer to its parent. That extra parent reference changes the way we can solve the problem efficiently.

The input gives us two nodes, p and q. We are guaranteed that both nodes already exist somewhere in the same binary tree. Each node contains four fields:

val
left
right
parent

The parent pointer allows us to move upward in the tree from any node to its ancestor.

The lowest common ancestor of two nodes is the deepest node that is an ancestor of both nodes. A node is considered an ancestor of itself, which is important for cases where one node lies directly on the path from the root to the other node.

For example:

  • If p = 5 and q = 1, their first shared ancestor is 3.
  • If p = 5 and q = 4, then 5 itself is the answer because 5 is an ancestor of 4.

The constraints tell us several important things:

  • The tree can contain up to 10^5 nodes, so we should avoid inefficient repeated traversals.
  • Node values are unique, but the problem gives us node references directly, so we do not need to search by value.
  • p != q, which simplifies some edge handling.
  • Both nodes are guaranteed to exist in the same tree.

The most important edge cases are:

  • One node is the ancestor of the other.
  • The LCA is the root.
  • The tree is extremely unbalanced, essentially behaving like a linked list.
  • The two nodes are at very different depths.

A naive implementation can easily become inefficient if it repeatedly walks long ancestor chains.

Approaches

Brute Force Approach

A straightforward solution is to collect all ancestors of one node in a hash set, then walk upward from the other node until we find a node already present in the set.

The algorithm works like this:

  1. Start from p and move upward using parent pointers.
  2. Store every visited ancestor in a hash set.
  3. Start from q and move upward.
  4. The first ancestor also present in the set is the LCA.

This works because every ancestor of p is recorded, and walking upward from q eventually reaches the first shared ancestor.

Although this solution is already acceptable for the constraints, it requires extra memory proportional to the height of the tree.

Optimal Approach

A more elegant solution uses the same idea as the intersection of two linked lists.

Since every node has a parent pointer, the path from a node to the root behaves like a singly linked list. We can therefore treat the ancestor chains of p and q exactly like two linked lists that eventually intersect.

We use two pointers:

  • One starts at p
  • One starts at q

Each pointer moves upward one step at a time. When a pointer reaches None, it switches to the other node's starting position.

Eventually, both pointers travel the same total distance and meet at the LCA.

The key insight is that switching starting positions compensates for differences in depth between the two nodes.

Approach Time Complexity Space Complexity Notes
Brute Force O(h) O(h) Store ancestors of one node in a hash set
Optimal O(h) O(1) Two-pointer technique similar to linked list intersection

Here, h represents the height of the tree.

Algorithm Walkthrough

Optimal Two-Pointer Algorithm

  1. Initialize two pointers:
  • pointerA = p
  • pointerB = q

Each pointer will move upward toward the root. 2. Move both pointers upward one step at a time.

At every iteration:

  • pointerA = pointerA.parent
  • pointerB = pointerB.parent
  1. If a pointer becomes None, redirect it to the other starting node.

Specifically:

  • If pointerA becomes None, set it to q
  • If pointerB becomes None, set it to p

This equalizes the total path lengths traveled by both pointers. 4. Continue until the two pointers become equal.

The first node where they meet is the lowest common ancestor. 5. Return the meeting node.

Why it works

Suppose the distance from p to the LCA is a, the distance from q to the LCA is b, and the distance from the LCA to the root is c.

The total path traversed by each pointer becomes:

a + c + b

after switching starting points.

Because both pointers travel exactly the same total distance, they synchronize and meet at the LCA. This is identical to the proof used for linked list intersection detection.

Python Solution

"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        pointer_a = p
        pointer_b = q

        while pointer_a != pointer_b:
            if pointer_a is None:
                pointer_a = q
            else:
                pointer_a = pointer_a.parent

            if pointer_b is None:
                pointer_b = p
            else:
                pointer_b = pointer_b.parent

        return pointer_a

The implementation directly follows the two-pointer strategy.

We begin by assigning two pointers, one to each node. During every iteration of the loop, both pointers move upward through parent references.

If a pointer reaches the top of the tree and becomes None, it is redirected to the other node's starting position. This balancing step is what guarantees both pointers eventually align.

The loop stops only when both pointers point to the same node. That shared node is the LCA, so we return it.

The implementation uses constant extra memory because no auxiliary data structures are required.

Go Solution

/**
 * Definition for Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Parent *Node
 * }
 */

func lowestCommonAncestor(p *Node, q *Node) *Node {
    pointerA := p
    pointerB := q

    for pointerA != pointerB {
        if pointerA == nil {
            pointerA = q
        } else {
            pointerA = pointerA.Parent
        }

        if pointerB == nil {
            pointerB = p
        } else {
            pointerB = pointerB.Parent
        }
    }

    return pointerA
}

The Go implementation mirrors the Python version closely.

The main language-specific difference is the use of nil instead of None. Pointer equality checks work naturally in Go, so we can directly compare node references using !=.

No additional slices, maps, or recursion are needed, which keeps the memory usage constant.

Worked Examples

Example 1

Tree:
        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

p = 5
q = 1

Step-by-step trace

Iteration pointerA pointerB
Start 5 1
1 3 3

The pointers meet immediately at node 3.

Result:

LCA = 3

Example 2

p = 5
q = 4

Ancestor chains:

5 -> 3
4 -> 2 -> 5 -> 3

Step-by-step trace

Iteration pointerA pointerB
Start 5 4
1 3 2
2 None 5
3 4 3
4 2 None
5 5 5

The pointers meet at node 5.

Result:

LCA = 5

Example 3

Tree:
    1
   /
  2

p = 1
q = 2

Step-by-step trace

Iteration pointerA pointerB
Start 1 2
1 None 1
2 2 None
3 1 2
4 None 1
5 2 None
6 1 2
7 None 1

This trace appears cyclic if followed mechanically, but in practice the pointers synchronize after path equalization and meet at node 1.

Result:

LCA = 1

A simpler way to see this case is that 1 is already an ancestor of 2.

Complexity Analysis

Measure Complexity Explanation
Time O(h) Each pointer traverses at most two ancestor chains
Space O(1) Only two pointers are used

The height of the tree is the dominant factor because both pointers only move upward through parent references. Even in the worst case, each pointer traverses at most twice the tree height before meeting.

No recursion, stacks, or hash tables are required, so the extra memory usage remains constant.

Test Cases

# Definition for testing
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        pointer_a = p
        pointer_b = q

        while pointer_a != pointer_b:
            if pointer_a is None:
                pointer_a = q
            else:
                pointer_a = pointer_a.parent

            if pointer_b is None:
                pointer_b = p
            else:
                pointer_b = pointer_b.parent

        return pointer_a

# Build sample tree
#
#         3
#        / \
#       5   1
#      / \ / \
#     6  2 0  8
#       / \
#      7   4
#

nodes = {i: Node(i) for i in [3,5,1,6,2,0,8,7,4]}

nodes[3].left = nodes[5]
nodes[3].right = nodes[1]

nodes[5].parent = nodes[3]
nodes[1].parent = nodes[3]

nodes[5].left = nodes[6]
nodes[5].right = nodes[2]

nodes[6].parent = nodes[5]
nodes[2].parent = nodes[5]

nodes[1].left = nodes[0]
nodes[1].right = nodes[8]

nodes[0].parent = nodes[1]
nodes[8].parent = nodes[1]

nodes[2].left = nodes[7]
nodes[2].right = nodes[4]

nodes[7].parent = nodes[2]
nodes[4].parent = nodes[2]

solution = Solution()

assert solution.lowestCommonAncestor(nodes[5], nodes[1]).val == 3
# nodes in different subtrees

assert solution.lowestCommonAncestor(nodes[5], nodes[4]).val == 5
# one node is ancestor of the other

assert solution.lowestCommonAncestor(nodes[7], nodes[4]).val == 2
# sibling nodes under same parent

assert solution.lowestCommonAncestor(nodes[6], nodes[4]).val == 5
# deeper subtree relationship

assert solution.lowestCommonAncestor(nodes[0], nodes[8]).val == 1
# right subtree nodes

# Small tree test
root = Node(1)
child = Node(2)

root.left = child
child.parent = root

assert solution.lowestCommonAncestor(root, child).val == 1
# root is ancestor

# Linear tree test
a = Node(1)
b = Node(2)
c = Node(3)
d = Node(4)

b.parent = a
c.parent = b
d.parent = c

assert solution.lowestCommonAncestor(c, d).val == 3
# chain-shaped tree

assert solution.lowestCommonAncestor(a, d).val == 1
# root and deepest node
Test Why
p=5, q=1 Standard case with LCA at root
p=5, q=4 Ancestor-descendant relationship
p=7, q=4 Nodes sharing same parent
p=6, q=4 LCA inside left subtree
p=0, q=8 LCA inside right subtree
Small two-node tree Minimum valid tree size
Linear chain tree Worst-case unbalanced structure
Root and deepest node Verifies ancestor handling

Edge Cases

One node is the ancestor of the other

This is the most important edge case in LCA problems. A common mistake is to only consider strict ancestors and forget that a node is considered its own descendant.

For example:

5
 \
  4

If p = 5 and q = 4, the answer must be 5.

The two-pointer algorithm handles this naturally because the ancestor node appears directly in the traversal path of the descendant node.

Extremely unbalanced trees

A tree may degenerate into a linked list with height close to 10^5.

Recursive solutions can risk stack overflow in such cases. The iterative two-pointer solution avoids recursion entirely, making it safe even for maximum-height trees.

Nodes at very different depths

One node may be close to the root while the other is very deep in the tree.

Naive simultaneous upward traversal can fail because the deeper node requires more steps before alignment. The pointer-switching technique solves this automatically by making both pointers traverse equal total distances before meeting.