Lowest Common Ancestor of a Binary Tree II
Asked at Atlassian
Problem
Given the root of a binary tree and two nodes p and q, return the lowest common ancestor (LCA) of p and q. Unlike the standard LCA problem, p and q may or may not exist in the tree. If either node is missing, return null.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | MEDIUM | View all Atlassian questions → |
How to Think About It
Brute force: do a full traversal to check if both p and q exist in the tree, then run standard LCA if they do.
Use a single DFS that simultaneously checks existence and finds LCA by returning a node or null.
Track whether p and q were found using a helper that returns a boolean or a special sentinel.
Post-order DFS: if the current node is p or q, mark it found. After recursing left and right, determine if both were found in subtrees.
Optimal: O(n) time single-pass DFS that returns the LCA if both exist, or null if either is missing.
Optimal Approach
Use a post-order DFS that returns a tuple or uses a reference variable to track whether both p and q were found. When the current node matches p or q, set a found flag. After recursing into left and right children, if both children returned non-null (meaning both targets exist in different subtrees), the current node is the LCA. If only one child returned non-null and the current node itself is the other target, the current node is also the LCA. If either p or q was never found anywhere in the tree, return null. This runs in O(n) time with a single pass.
What Trips People Up in Real Interviews
The key difference from standard LCA: you must verify both nodes exist before returning an answer.
A common bug is returning an ancestor when only one node exists in the subtree.
Use a reference flag or a wrapper return type to communicate existence information up the recursion.
If p is an ancestor of q (or vice versa) and both exist, the ancestor is the correct LCA.
Edge case: p and q are the same node. If that node exists, it is its own LCA.
Solution Code
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
self.found_p = False
self.found_q = False
def dfs(node):
if not node:
return None
left = dfs(node.left)
right = dfs(node.right)
if node == p:
self.found_p = True
return node
if node == q:
self.found_q = True
return node
if left and right:
return node
return left if left else right
result = dfs(root)
if self.found_p and self.found_q:
return result
return NoneFrequently Asked Questions
What is the Lowest Common Ancestor of a Binary Tree II problem?
Given the root of a binary tree and two nodes p and q, return the lowest common ancestor (LCA) of p and q. Unlike the standard LCA problem, p and q may or may not exist in the tree. If either node is missing, return null.
How do you solve Lowest Common Ancestor of a Binary Tree II?
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 II?
Lowest Common Ancestor of a Binary Tree II is asked at Atlassian. It is a medium difficulty problem.
What are common mistakes on Lowest Common Ancestor of a Binary Tree II?
- The key difference from standard LCA: you must verify both nodes exist before returning an answer.
- A common bug is returning an ancestor when only one node exists in the subtree.
- Use a reference flag or a wrapper return type to communicate existence information up the recursion.
- If p is an ancestor of q (or vice versa) and both exist, the ancestor is the correct LCA.
- Edge case: p and q are the same node. If that node exists, it is its own LCA.