The Leetcode problem "Lowest Common Ancestor of a Binary Tree II" asks you to find the lowest common ancestor (LCA) of two given nodes, p and q, in a binary tree rooted at root. However, there is an important twist: either or both of the nodes p and q may not exist in the tree. If either p or q does not exist in the tree, you should return null (or None in Python).
p and q exist in the tree.p and q as descendants (a node can be a descendant of itself).p or q does not exist, return null.
The classic LCA problem assumes both target nodes exist in the tree. In that case, we can use a simple recursive approach: if the current node matches either p or q, we return it; otherwise, we search both left and right subtrees for the targets. If both subtrees return non-null, the current node is the LCA.
However, since p or q may not exist, we need to be careful. We can't just return the node where both sides meet; we must also make sure that both p and q are actually present in the tree. A brute-force way would be to search the tree twice to check for existence, then do the normal LCA search. But this is inefficient.
Instead, we can enhance our recursive function to not only look for the LCA, but also tell us whether p and q were found in the subtree. This way, we can combine existence checking and LCA finding in a single traversal.
We will use a recursive helper function that, for each node, returns three things:
null).p was found in this subtree.q was found in this subtree.null, return (null, false, false).
p or q.
p or q was found in this subtree.
p and q were found, return the LCA; otherwise, return null.
This approach ensures we only traverse the tree once and handle all cases efficiently.
Suppose we have the following tree:
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
Let p = 5 and q = 4. Both exist in the tree.
p).q) and right (2).q).q.p (itself) and q (from its right subtree) are both found. So, 5 is the LCA.p and q were found, we return 5.
If q = 42 (which doesn't exist), our function will traverse the tree, find p but not q, so it returns null.
Brute-force approach: Search for p and q separately (O(N) each), then find LCA (O(N)). Total: O(N) time, but with multiple traversals.
Optimized approach (ours): Single tree traversal, each node visited once. So, O(N) time, where N is the number of nodes.
Space complexity: O(H), where H is the height of the tree, for the recursion stack. For a balanced tree, this is O(log N); for a skewed tree, O(N).
We solved the "Lowest Common Ancestor of a Binary Tree II" problem by augmenting the standard LCA algorithm to also check for the existence of both target nodes in a single traversal. By returning flags up the recursive call stack, we efficiently determine if both targets exist and, if so, return their LCA. This approach is elegant because it combines existence checking and LCA finding into one pass, ensuring optimal performance.
class Solution:
def lowestCommonAncestor(self, root, p, q):
def helper(node):
if not node:
return (None, False, False)
left_lca, left_p, left_q = helper(node.left)
right_lca, right_p, right_q = helper(node.right)
found_p = left_p or right_p or node == p
found_q = left_q or right_q or node == q
# If node is LCA
if node == p or node == q:
return (node, found_p, found_q)
if left_lca and right_lca:
return (node, found_p, found_q)
if left_lca:
return (left_lca, found_p, found_q)
if right_lca:
return (right_lca, found_p, found_q)
return (None, found_p, found_q)
lca, found_p, found_q = helper(root)
return lca if found_p and found_q else None
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
struct Result {
TreeNode* lca;
bool found_p;
bool found_q;
};
Result helper(TreeNode* node, TreeNode* p, TreeNode* q) {
if (!node) return {nullptr, false, false};
Result left = helper(node->left, p, q);
Result right = helper(node->right, p, q);
bool found_p = left.found_p || right.found_p || node == p;
bool found_q = left.found_q || right.found_q || node == q;
if (node == p || node == q) {
return {node, found_p, found_q};
}
if (left.lca && right.lca) {
return {node, found_p, found_q};
}
if (left.lca) {
return {left.lca, found_p, found_q};
}
if (right.lca) {
return {right.lca, found_p, found_q};
}
return {nullptr, found_p, found_q};
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
Result res = helper(root, p, q);
return (res.found_p && res.found_q) ? res.lca : nullptr;
}
};
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private static class Result {
TreeNode lca;
boolean foundP, foundQ;
Result(TreeNode lca, boolean foundP, boolean foundQ) {
this.lca = lca;
this.foundP = foundP;
this.foundQ = foundQ;
}
}
private Result helper(TreeNode node, TreeNode p, TreeNode q) {
if (node == null) return new Result(null, false, false);
Result left = helper(node.left, p, q);
Result right = helper(node.right, p, q);
boolean foundP = left.foundP || right.foundP || node == p;
boolean foundQ = left.foundQ || right.foundQ || node == q;
if (node == p || node == q) {
return new Result(node, foundP, foundQ);
}
if (left.lca != null && right.lca != null) {
return new Result(node, foundP, foundQ);
}
if (left.lca != null) {
return new Result(left.lca, foundP, foundQ);
}
if (right.lca != null) {
return new Result(right.lca, foundP, foundQ);
}
return new Result(null, foundP, foundQ);
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Result res = helper(root, p, q);
return (res.foundP && res.foundQ) ? res.lca : null;
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
function helper(node) {
if (!node) return {lca: null, foundP: false, foundQ: false};
let left = helper(node.left);
let right = helper(node.right);
let foundP = left.foundP || right.foundP || node === p;
let foundQ = left.foundQ || right.foundQ || node === q;
if (node === p || node === q) {
return {lca: node, foundP, foundQ};
}
if (left.lca && right.lca) {
return {lca: node, foundP, foundQ};
}
if (left.lca) {
return {lca: left.lca, foundP, foundQ};
}
if (right.lca) {
return {lca: right.lca, foundP, foundQ};
}
return {lca: null, foundP, foundQ};
}
let result = helper(root);
return (result.foundP && result.foundQ) ? result.lca : null;
};