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:
[1, 104].-109 <= Node.val <= 109Node.val are unique.p != qFollow up: Can you find the LCA traversing the tree, without checking nodes existence?
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.
Python
Java
C++
JavaScript
| 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 |
LOWEST COMMON ANCESTOR OF A BINARY TREE II | PYTHON | LEETCODE 1644 • Cracking FAANG • 9,107 views views
Watch 9 more video solutions →Practice Lowest Common Ancestor of a Binary Tree II with our built-in code editor and test cases.
Practice on FleetCode