Lowest Common Ancestor of a Binary Tree III
Asked at Atlassian
Problem
Given a binary tree where each node has a parent pointer in addition to left and right children, find the lowest common ancestor of two nodes p and q. The parent pointer of the root is null. Both p and q are guaranteed to exist in the tree.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | MEDIUM | View all Atlassian questions → |
How to Think About It
Brute force: collect all ancestors of p in a set, then walk up from q until you find the first node in the set.
Use a hash set to store all ancestors of p while traversing up, then check ancestors of q against the set.
Two-pointer approach: start two pointers at p and q, walk them up simultaneously. When a pointer reaches null, redirect it to the other node.
The two-pointer trick works because both pointers travel the same total distance (len(p path) + len(q path) - shared) before meeting.
Optimal: O(n) time and O(1) space with two pointers, or O(n) time and O(depth) space with the hash set approach.
Optimal Approach
The most intuitive approach uses a hash set: traverse upward from p storing all ancestors, then traverse upward from q returning the first ancestor found in the set. The two-pointer approach is more elegant and uses O(1) space: start one pointer at p and another at q, move both up one step at a time. When a pointer reaches null, redirect it to the other node. Since both pointers travel the combined path length (depth of p + depth of q - 2 * depth of LCA), they will meet at the LCA. This works because the extra steps one pointer takes past the root are exactly compensated by the redirect.
What Trips People Up in Real Interviews
Clarify that each node has a parent pointer, unlike the standard binary tree LCA problem.
The hash set approach is the most intuitive: store p ancestors, walk q up until you hit a common node.
The two-pointer approach is elegant: if p and q are at different depths, the shorter path wraps around and the pointers meet at the LCA.
Key insight for two pointers: after pointer A reaches root, redirect to q. When pointer B reaches root, redirect to p. They will meet at the LCA.
Edge case: if p is an ancestor of q, the LCA is p. Both approaches handle this correctly.
Solution Code
class Solution:
def lowestCommonAncestor(self, p: Node, q: Node) -> Node:
a, b = p, q
while a != b:
a = a.parent if a.parent else q
b = b.parent if b.parent else p
return aFrequently Asked Questions
What is the Lowest Common Ancestor of a Binary Tree III problem?
Given a binary tree where each node has a parent pointer in addition to left and right children, find the lowest common ancestor of two nodes p and q. The parent pointer of the root is null. Both p and q are guaranteed to exist in the tree.
How do you solve Lowest Common Ancestor of a Binary Tree III?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Lowest Common Ancestor of a Binary Tree III?
Lowest Common Ancestor of a Binary Tree III is asked at Atlassian. It is a medium difficulty problem.
What are common mistakes on Lowest Common Ancestor of a Binary Tree III?
- Clarify that each node has a parent pointer, unlike the standard binary tree LCA problem.
- The hash set approach is the most intuitive: store p ancestors, walk q up until you hit a common node.
- The two-pointer approach is elegant: if p and q are at different depths, the shorter path wraps around and the pointers meet at the LCA.
- Key insight for two pointers: after pointer A reaches root, redirect to q. When pointer B reaches root, redirect to p. They will meet at the LCA.
- Edge case: if p is an ancestor of q, the LCA is p. Both approaches handle this correctly.