MediumTreeDepth-First SearchBinary TreeBinary LiftingLowest Common AncestorUpdated Sep 2026

1644. Lowest Common Ancestor of a Binary Tree II

Asked at Atlassian

Difficulty

Medium

Time

O(n)

Space

O(h)

Pattern

Tree

Companies

1

Problem

You are given the root of a binary tree and two nodes, p and q. Return the lowest common ancestor (LCA) of p and q.

The LCA is the deepest node in the tree that has both p and q in its subtree. A node counts as a descendant of itself, so if p is an ancestor of q, the answer is p.

The twist: p and q are not guaranteed to be in the tree. If either of them is missing, return null. All node values are unique, so you can compare nodes by identity or by value.

Find the deepest node holding both targets

65p = 57243answer = 301q = 18The lowest node whose subtree contains both p and q is the root 3.
Node 5 sits on the left side and node 1 on the right side, so their paths meet at the root 3.

Constraints

  • ●The number of nodes in the tree is in the range [1, 10^4].
  • ●-10^9 <= Node.val <= 10^9
  • ●All Node.val are unique.
  • ●p != q

Examples

Example 1
Inputroot = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output3
WhyNode 5 lives in the left subtree of 3, and node 1 lives in the right subtree. The first node that has both of them below it is 3, so 3 is the answer.
Example 2
Inputroot = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output5
WhyNode 4 is a descendant of node 5, and a node is allowed to be its own descendant. So the lowest node containing both is 5 itself.
Example 3
Inputroot = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10
Outputnull
WhyNode 10 never appears in the tree. Since one target is missing, we must return null even though node 5 exists.

Asked At

1 companies
CompanyDifficulty
AtlassianMediumView all Atlassian questions →

How to Think About It

1

Brute force: do a full traversal to check if both p and q exist in the tree, then run standard LCA if they do.

2

Use a single DFS that simultaneously checks existence and finds LCA by returning a node or null.

3

Track whether p and q were found using a helper that returns a boolean or a special sentinel.

4

Post-order DFS: if the current node is p or q, mark it found. After recursing left and right, determine if both were found in subtrees.

5

Optimal: O(n) time single-pass DFS that returns the LCA if both exist, or null if either is missing.

Optimal Approach

Use a post-order DFS that returns a tuple or uses a reference variable to track whether both p and q were found. When the current node matches p or q, set a found flag. After recursing into left and right children, if both children returned non-null (meaning both targets exist in different subtrees), the current node is the LCA. If only one child returned non-null and the current node itself is the other target, the current node is also the LCA. If either p or q was never found anywhere in the tree, return null. This runs in O(n) time with a single pass.

One post-order DFS returns a node upward

65returns 5724301returns 18Step 1 — the left subtree returns p = 5 and the right subtree returns q = 1.657243left and right both set → return 3018Step 2 — the root sees a non-null result from both children, so it is the LCA.dfs(node) returns p, q, or LCAboth children non-null → node is LCAone side non-null → pass it upif p or q never seen → return null
Each call returns p, q, or the LCA found so far; the root combines the two sides.
ComplexityTime O(n)Space O(h)Each node is visited once in a single DFS, and h is the tree height for the recursion stack.

What Trips People Up in Real Interviews

1

The key difference from standard LCA: you must verify both nodes exist before returning an answer.

2

A common bug is returning an ancestor when only one node exists in the subtree.

3

Use a reference flag or a wrapper return type to communicate existence information up the recursion.

4

If p is an ancestor of q (or vice versa) and both exist, the ancestor is the correct LCA.

5

Edge case: p and q are the same node. If that node exists, it is its own LCA.

Solution Code

O(n) time
class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        self.found_p = False
        self.found_q = False

        def dfs(node):
            if not node:
                return None
            left = dfs(node.left)
            right = dfs(node.right)
            if node == p:
                self.found_p = True
                return node
            if node == q:
                self.found_q = True
                return node
            if left and right:
                return node
            return left if left else right

        result = dfs(root)
        if self.found_p and self.found_q:
            return result
        return None

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Lowest Common Ancestor of a Binary Tree II problem?

Given the root of a binary tree and two nodes p and q, return the lowest common ancestor (LCA) of p and q. Unlike the standard LCA problem, p and q may or may not exist in the tree. If either node is missing, return null.

How do you solve Lowest Common Ancestor of a Binary Tree II?

The optimal approach runs in O(n) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Lowest Common Ancestor of a Binary Tree II?

Lowest Common Ancestor of a Binary Tree II is asked at Atlassian. It is a medium difficulty problem.

What are common mistakes on Lowest Common Ancestor of a Binary Tree II?
  • The key difference from standard LCA: you must verify both nodes exist before returning an answer.
  • A common bug is returning an ancestor when only one node exists in the subtree.
  • Use a reference flag or a wrapper return type to communicate existence information up the recursion.
  • If p is an ancestor of q (or vice versa) and both exist, the ancestor is the correct LCA.
  • Edge case: p and q are the same node. If that node exists, it is its own LCA.