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.
We use a hash table vis to record all nodes on the path from node p to the root node. Then we start from node q and traverse towards the root node. If we encounter a node that exists in the hash table vis, then this node is the nearest common ancestor of p and q, and we can return it directly.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
We can use two pointers a and b to point to nodes p and q respectively, and then traverse towards the root node. When a and b meet, it is the nearest common ancestor of p and q. Otherwise, if pointer a traverses to the root node, then we let it point to node q, and do the same for pointer b. In this way, when the two pointers meet, it is the nearest common ancestor of p and q.
The time complexity is O(n), where n is the number of nodes in the binary tree. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Hash Table | — |
| Two Pointers | — |
| 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 |
LOWEST COMMON ANCESTOR OF A BINARY TREE III [PYTHON] • Cracking FAANG • 21,968 views views
Watch 9 more video solutions →Practice Lowest Common Ancestor of a Binary Tree III with our built-in code editor and test cases.
Practice on FleetCode