Binary Tree Common Ancestor Node — Problem Statement & Solution Guide
Problem Description
Given the root of a binary tree and two distinct integer values, targetA and targetB, determine the Lowest Common Ancestor (LCA) of the nodes containing these values. The LCA is defined as the deepest node in the tree that has both targetA and targetB in its respective subtrees (including itself). A node is considered an ancestor of itself. If either targetA or targetB does not exist in the tree, the function must return null. The tree is guaranteed to have unique node values.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Binary Tree Common Ancestor Node"
WHY DOES IT MATTER?
Finding the LCA is a classic example of leveraging tree recursion to combine sub‑problem results, a pattern that recurs in many hierarchical data problems such as permission checks, version control merges, and network routing.
OPTIMIZATION CHALLENGE
The key insight is to propagate a boolean (or count) flag up the recursion stack, allowing the algorithm to decide the LCA at the moment both targets are discovered, thus avoiding extra passes or auxiliary data structures.
REAL-WORLD CONNECTION
In distributed systems, the LCA mirrors the concept of the nearest common coordinator in a hierarchy of services—identifying the minimal service that can mediate between two downstream components without traversing the entire network.
During an interview, code the recursive helper first to return a tuple (foundA, foundB, node) and let the caller decide; this keeps the logic clean and makes it easy to handle missing targets without extra conditionals.
COMPLEXITY AT A GLANCE
O(n)O(h)Core Theory — Why This Approach?
The Lowest Common Ancestor (LCA) problem on a binary tree can be solved efficiently using a single post‑order traversal that returns information about the presence of the two target values in each subtree. The algorithm works by recursively exploring left and right children; each call reports whether it has found targetA, targetB, or the LCA itself. When a node receives a positive report from both sides (or one side plus itself), it becomes the LCA because it is the deepest node where the two targets diverge. This divide‑and‑conquer paradigm leverages the tree’s hierarchical structure, guaranteeing that each node is visited exactly once, yielding linear time.
A naive approach would enumerate all ancestors of each target by traversing from the root to each node, store them in hash sets, and then intersect the sets. While conceptually simple, it requires two full traversals to locate the nodes and additional O(h) extra space per path, where h is the tree height. In the worst case of a skewed tree, this degrades to O(n) time but with extra overhead and complexity in handling missing nodes. The optimal single‑pass recursion eliminates the need for explicit ancestor storage and naturally handles the case where one or both targets are absent, making it both time‑optimal (O(n)) and space‑optimal (O(h) call stack).
Interview Questions on This Problem
Q1How would you modify the LCA algorithm to work on a binary search tree (BST) and achieve O(h) time?
In a BST, you can exploit the ordering property: start at the root and compare both targets to the current node's value. If both are smaller, move left; if both are larger, move right; otherwise the current node is the LCA. This runs in O(h) where h is the height of the BST.
Q2What changes are required if the tree is not a binary tree but an N‑ary tree?
Replace the two recursive calls with a loop over all children. The function should return the count of targets found in the subtree; when the count reaches 2 at a node, that node is the LCA. The overall complexity stays O(n) with O(h) recursion depth.
Q3How can you adapt the LCA solution to handle the case where the tree is stored as parent pointers only (no child links)?
First, build the path from each target up to the root using parent pointers, store one path in a hash set, then walk the second path upward until you encounter a node in the set; that node is the LCA. This runs in O(h) time and O(h) extra space.
Examples
Input
root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], targetA = 5, targetB = 1
Output
3
Explanation: The node with value 5 is in the left subtree of root 3. The node with value 1 is in the right subtree of root 3. Since 3 is the first node where the paths to 5 and 1 diverge, 3 is the LCA.
Input
root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], targetA = 5, targetB = 4
Output
5
Explanation: The node with value 4 is a descendant of node 5. Since a node is an ancestor of itself, and 5 is the deepest node that contains both 5 and 4 in its subtree, 5 is the LCA.
Input
root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], targetA = 6, targetB = 9
Output
null
Explanation: The value 9 does not exist in the tree. According to the problem constraints, if either target value is missing, the function returns null.
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.
- targetA != targetB.
- targetA and targetB exist in the tree or one of them is missing.
Optimal Approach & Strategy
The optimal solution performs a single depth‑first search, returning flags for the presence of each target and bubbling up the first node where both flags are true. This eliminates extra storage and extra passes.
Brute Force Approach
A naive method records the full ancestor path for each target by traversing from the root, then scans both paths from the root to find the last common node. This needs two full traversals and extra O(h) space for each path.
Verified Code Solutions
function lowestCommonAncestor(root, p, q) {
if (!root) return null;
if (root.val === p.val || root.val === q.val) return root;
let left = lowestCommonAncestor(root.left, p, q);
let right = lowestCommonAncestor(root.right, p, q);
if (left && right) return root;
return left ? left : right;
}class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return nullptr;
if (root->val == p->val || root->val == q->val) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root;
return left ? left : right;
}
};class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
if (root.val == p.val || root.val == q.val) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
}
}class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def lowestCommonAncestor(root, p, q):
if not root:
return None
if root.val == p.val or root.val == q.val:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left if left else rightfunction lowestCommonAncestor(root, p, q) {
if (!root) return null;
if (root.val === p.val || root.val === q.val) return root;
let left = lowestCommonAncestor(root.left, p, q);
let right = lowestCommonAncestor(root.right, p, q);
if (left && right) return root;
return left ? left : right;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.