Watch 10 video solutions for Lowest Common Ancestor of a Binary Tree III, a medium level problem involving Hash Table, Two Pointers, Tree. This walkthrough by Cracking FAANG has 21,968 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).
Each node will have a reference to its parent node. The definition for Node is below:
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}
According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)."
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:
[2, 105].-109 <= Node.val <= 109Node.val are unique.p != qp and q exist in the tree.Problem Overview: Given two nodes in a binary tree where each node has a pointer to its parent, return their lowest common ancestor (LCA). The LCA is the deepest node that has both nodes as descendants. Because parent pointers exist, you can traverse upward from any node instead of starting at the root.
Approach 1: Hash Table (O(h) time, O(h) space)
Start from node p and walk upward through its parent pointers while storing every visited node in a hash set. Then move upward from node q, checking at each step whether the node already exists in the set. The first match is the lowest common ancestor. The key insight: all ancestors of p form a path to the root, so the first ancestor of q that intersects this path must be the LCA. This approach relies on constant-time hash lookups and works for any binary tree structure. Time complexity is O(h), where h is the tree height, and space complexity is also O(h) due to the stored ancestors.
Approach 2: Two Pointers (O(h) time, O(1) space)
This approach treats the ancestor chains like two linked lists. Use two pointers starting at p and q. Move each pointer upward using the parent pointer. When a pointer reaches null, redirect it to the other node's starting position. Eventually both pointers traverse equal path lengths and meet at the LCA. The trick works because both pointers cover the combined depth of both nodes, similar to the classic intersection-of-linked-lists technique. Time complexity is O(h) and space complexity is O(1), making it the most space-efficient solution.
Both approaches rely on traversing parent pointers rather than exploring children from the root. That changes the typical tree traversal pattern and makes the problem closer to path intersection. The first solution uses a hash table to track visited ancestors, while the second uses a pointer-switching trick commonly seen in two pointers problems.
Recommended for interviews: The two-pointer approach is usually preferred because it achieves O(1) extra space while keeping the same O(h) time complexity. Still, explaining the hash set method first clearly demonstrates your reasoning: store one path, intersect with the other. Showing both approaches signals strong problem-solving depth.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Table (Ancestor Set) | O(h) | O(h) | When you want a straightforward implementation and quick ancestor lookup |
| Two Pointers (Parent Traversal) | O(h) | O(1) | Best general solution when minimizing extra memory is preferred |