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

Description Hints 2 Solution Video 20:46

1644. Lowest Common Ancestor of a Binary Tree II

Medium69.6% acceptance4 companiesPremium elsewhere, free here

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, 10⁴].
-10⁹ <= Node.val <= 10⁹
All Node.val are unique.
p != q

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

Asked at 4 companies

LinkedIn Meta Atlassian Microsoft

Topics

Hints open one at a time

Hint 1

Traverse the graph visiting root, left, root, right, root to make an Euler Path

Hint 2

Return the node (LCA) that is at the lowest depth between p and q in the Euler Path

20:46

Still stuck?Read the written solution, or watch a walkthrough.

Open solution