[Medium] 1650. Lowest Common Ancestor of a Binary Tree III

Difficulty: Medium
Category: Tree, Binary Tree, LCA

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.

Thinking Process

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:

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

Key Insight:

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

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Recursive DFS	O(n)	O(h)	Depth, path sum, subtree queries
BFS level-order	O(n)	O(w)	Level traversal, zigzag
Inorder on BST	O(n)	O(h)	Sorted order, successor
Divide & conquer on tree (this problem)	O(n)	O(h)	Diameter, max path

Solution

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

Solution Explanation

See Complexity below for time and space analysis.

Explanation

Step-by-Step Process:

Initialize pointers: a = p, b = q
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
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

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 Concepts

Lowest Common Ancestor: Deepest node that has both nodes as descendants
Parent Pointer: Each node knows its parent (unlike standard binary tree)
Two-Pointer Technique: Classic algorithm pattern for finding intersections
Distance Equalization: Mathematical insight that makes the algorithm work
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.

References

LC 1650: Lowest Common Ancestor of a Binary Tree III on LeetCode
LeetCode Discuss — LC 1650: Lowest Common Ancestor of a Binary Tree III
LeetCode Editorial (may require premium)

Common Mistakes

Skipping edge cases (empty input, single element, boundaries).
Off-by-one errors in loops and index ranges.
Forgetting to handle the case when no valid answer exists.

Key Takeaways

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

Robina Li