Skip to main content
Talentd

Lowest Common Ancestor of a Binary Tree II - Solution & Explanation

MediumPremiumFree on FleetCodeTreeDepth-First SearchBinary Tree6 min readAsked at: Microsoft, Meta, Atlassian +1
Practice this problem

Problem Statement

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.val are unique.
  • p != q

 

Follow up: Can you find the LCA traversing the tree, without checking nodes existence?

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

Code

PythonJavaC++JavaScript

Python

Java

C++

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Standard LCA + Existence CheckO(n)O(h)When adapting the classic LCA template and clarity matters more than minimizing traversals
Single-Pass DFS with Presence TrackingO(n)O(h)Best general solution; finds LCA and verifies both nodes in one traversal

Video Solution

LOWEST COMMON ANCESTOR OF A BINARY TREE II | PYTHON | LEETCODE 1644 • Cracking FAANG • 9,238 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Lowest Common Ancestor of a Binary Tree II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Lowest Common Ancestor of a Binary Search Tree

Next

Lowest Common Ancestor of a Binary Tree