Lowest Common Ancestor of a Binary Tree II solution and explanation
9 more videos on this problem
LOWEST COMMON ANCESTOR OF A BINARY TREE II | PYTHON | LEETCODE 1644Cracking FAANG · 20:46 · 9K views
LeetCode 1644. Lowest Common Ancestor of a Binary Tree II | Locked Question宰相小甘罗 · 7:58 · 1K views
LeetCode 1644. Lowest Common Ancestor of a Binary Tree II 中文 | 加锁题宰相小甘罗 · 6:44 · 1K views
1644. Lowest Common Ancestor of a Binary Tree II - Week 3/5 Leetcode July ChallengeProgramming Live with Larry · 5:02 · 455 views
Lowest Common Ancestor of a Binary Tree II - LeetCode 1644 - PythonAlpha-Code · 15:25 · 411 views
1644. Lowest Common Ancestor of a Binary Tree II - Week 4/5 Leetcode December ChallengeProgramming Live with Larry · 5:32 · 179 views
Leetcode 1644. Lowest Common Ancestor of a Binary Tree II (LCA)LetsCode · 4:55 · 45 views
Facing the LeetCode Gauntlet: Day 1 - 1644. Lowest Common Ancestor of a Binary Tree IIStruggling CS Student · 20:51 · 26 views
Lowest Common Ancestor of a Binary Tree II (LeetCode 1644)Coding Blizz · 15:20 · 21 views
Leetcode 1644 (medium) - Lowest Common Ancestor of a Binary Tree IITechStack in Motion · 6:28 · 3 views
The problem
Given the root of a binary tree, return the lowest common ancestor (LCA) of two given nodes, p and q. If either node p or q does not exist in the tree, return null. All values of the nodes in the tree are unique.
According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a binary 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)". A descendant of a node x is a node y that is on the path from node x to some leaf node.
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. A node can be a descendant of itself according to the definition of LCA.
Example 3:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10 Output: null Explanation: Node 10 does not exist in the tree, so return null.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -109 <= Node.val <= 109- All
Node.valare unique. p != q
Approach overview
Problem Overview: Given the root of a binary tree and two nodes p and q, return their lowest common ancestor (LCA). The twist compared to the classic LCA problem: either node might not exist in the tree. If one or both nodes are missing, the result must be null.
Approach 1: Standard LCA + Existence Check (DFS) (Time: O(n), Space: O(h))
First compute the LCA using the classic recursive algorithm for a binary tree. The recursion explores left and right subtrees using Depth-First Search. If the current node matches p or q, return it. When both recursive calls return non-null values, the current node becomes the LCA. Because this variant allows missing nodes, run an additional DFS to confirm that both p and q actually appear in the tree.
This method separates the logic into two phases: compute a candidate ancestor, then validate presence. The main advantage is simplicity because it reuses the well-known LCA pattern from tree problems. The drawback is that you may traverse the tree more than once.
Approach 2: Single-Pass DFS with Node Presence Tracking (Time: O(n), Space: O(h))
Perform a single DFS that returns a potential LCA while simultaneously tracking whether p and q were found. Each recursive call checks the current node and explores its left and right children. Maintain boolean flags indicating whether either target node has been discovered during traversal. If both sides return non-null results, the current node becomes the LCA candidate.
During traversal, update global or reference flags when p or q are encountered. After DFS completes, return the candidate LCA only if both flags are true; otherwise return null. This approach ensures the tree is scanned only once while solving both the ancestor discovery and existence validation.
Recommended for interviews: The single-pass DFS approach is what interviewers typically expect. It demonstrates a strong understanding of recursive tree traversal and avoids redundant passes through the tree. Explaining the two-pass solution first shows you understand the base LCA problem, while the optimized single DFS highlights algorithmic efficiency.
Solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(
self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'
) -> 'TreeNode':
def dfs(root, p, q):
if root is None:
return False
l = dfs(root.left, p, q)
r = dfs(root.right, p, q)
nonlocal ans
if l and r:
ans = root
if (l or r) and (root.val == p.val or root.val == q.val):
ans = root
return l or r or root.val == p.val or root.val == q.val
ans = None
dfs(root, p, q)
return ans/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private TreeNode ans;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root, p, q);
return ans;
}
private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return false;
}
boolean l = dfs(root.left, p, q);
boolean r = dfs(root.right, p, q);
if (l && r) {
ans = root;
}
if ((l || r) && (root.val == p.val || root.val == q.val)) {
ans = root;
}
return l || r || root.val == p.val || root.val == q.val;
}
}/**
* 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:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
dfs(root, p, q);
return ans;
}
private:
TreeNode* ans = nullptr;
bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) {
return false;
}
bool l = dfs(root->left, p, q);
bool r = dfs(root->right, p, q);
if (l && r) {
ans = root;
}
if ((l || r) && (root->val == p->val || root->val == q->val)) {
ans = root;
}
return l || r || root->val == p->val || root->val == q->val;
}
};/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function (root, p, q) {
const dfs = root => {
if (!root) {
return false;
}
const l = dfs(root.left);
const r = dfs(root.right);
if (l && r) {
ans = root;
}
if ((l || r) && (root.val === p.val || root.val === q.val)) {
ans = root;
}
return l || r || root.val === p.val || root.val === q.val;
};
let ans = null;
dfs(root);
return ans;
};Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Standard LCA + Existence Check | O(n) | O(h) | When adapting the classic LCA template and clarity matters more than minimizing traversals |
| Single-Pass DFS with Presence Tracking | O(n) | O(h) | Best general solution; finds LCA and verifies both nodes in one traversal |
Frequently asked questions
Is Lowest Common Ancestor of a Binary Tree II easy or hard?
Lowest Common Ancestor of a Binary Tree II is generally considered a medium-level tree problem. The base LCA algorithm is standard, but the additional constraint that nodes may not exist requires careful handling and validation during traversal.
Lowest Common Ancestor of a Binary Tree II Python/Java solution
Typical solutions use a recursive DFS helper function. The function returns a node if it matches p or q, or if both children return valid nodes. Implementations in Python, Java, C++, and JavaScript follow the same recursive pattern with O(n) time and O(h) space complexity.
How to solve Lowest Common Ancestor of a Binary Tree II in O(n)?
Run a DFS that explores left and right subtrees while checking if the current node equals p or q. If both subtrees return non-null results, the current node is the LCA. Track whether both nodes were actually found during traversal and only return the LCA if both exist. This guarantees a single O(n) traversal.
What is the best approach for Lowest Common Ancestor of a Binary Tree II?
The best approach uses a single Depth-First Search traversal that simultaneously computes the LCA and verifies whether both nodes exist in the tree. The recursion returns potential ancestors while tracking discovery flags for p and q. This runs in O(n) time with O(h) recursion stack space, where h is the tree height.
Is Lowest Common Ancestor of a Binary Tree II asked at Google/Amazon/Meta?
Lowest Common Ancestor problems are common in interviews at companies like Google, Amazon, and Meta because they test recursion, tree traversal, and reasoning about hierarchical structures. Variants such as missing-node cases or parent-pointer trees frequently appear in technical rounds.
What data structure is used in Lowest Common Ancestor of a Binary Tree II?
The problem uses a binary tree along with recursive Depth-First Search traversal. The algorithm relies on the call stack to propagate potential ancestors upward while checking whether the target nodes appear in each subtree.
What is the time complexity of Lowest Common Ancestor of a Binary Tree II?
The optimal solution runs in O(n) time because every node in the binary tree may need to be visited once during DFS. Space complexity is O(h) due to the recursion stack, where h represents the height of the tree (O(log n) for balanced trees and O(n) for skewed trees).