MediumHash TableTwo PointersTreeBinary TreeBinary LiftingLowest Common AncestorUpdated Sep 2026

1650. Lowest Common Ancestor of a Binary Tree III

Asked at Atlassian

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Hash Table

Companies

1

Problem

You are given two nodes, p and q, inside a binary tree. Every node in this tree has three pointers: left, right, and parent. The root's parent is null. Your job is to return the lowest common ancestor (LCA) of p and q.

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

You do not get the root. You only get the two nodes. But because each node points to its parent, you can walk upward from either node toward the root. Both p and q are guaranteed to exist in the tree, and p != q.

Find the deepest shared ancestor

65p = 57243LCA = 301q = 18Node 3 is the deepest node that contains both 5 and 1.
Walking up from 5 gives 5, 3. Walking up from 1 gives 1, 3. The first shared node is 3.

Constraints

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

Examples

Example 1
Inputroot = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output3
WhyNode 5 sits in the left subtree of 3, and node 1 sits in the right subtree of 3. The first node that has both of them below it is 3.
Example 2
Inputroot = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output5
WhyNode 4 is a child of 2, which is a child of 5. So 5 is already an ancestor of 4, and a node is allowed to be its own descendant. The answer is 5.
Example 3
Inputroot = [1,2], p = 1, q = 2
Output1
WhyThe tree is just 1 with child 2. Node 1 is the parent of 2, so it is the lowest node containing both.

Asked At

1 companies
CompanyDifficulty
AtlassianMediumView all Atlassian questions →

How to Think About It

1

Brute force: collect all ancestors of p in a set, then walk up from q until you find the first node in the set.

2

Use a hash set to store all ancestors of p while traversing up, then check ancestors of q against the set.

3

Two-pointer approach: start two pointers at p and q, walk them up simultaneously. When a pointer reaches null, redirect it to the other node.

4

The two-pointer trick works because both pointers travel the same total distance (len(p path) + len(q path) - shared) before meeting.

5

Optimal: O(n) time and O(1) space with two pointers, or O(n) time and O(depth) space with the hash set approach.

Optimal Approach

The most intuitive approach uses a hash set: traverse upward from p storing all ancestors, then traverse upward from q returning the first ancestor found in the set. The two-pointer approach is more elegant and uses O(1) space: start one pointer at p and another at q, move both up one step at a time. When a pointer reaches null, redirect it to the other node. Since both pointers travel the combined path length (depth of p + depth of q - 2 * depth of LCA), they will meet at the LCA. This works because the extra steps one pointer takes past the root are exactly compensated by the redirect.

Two pointers that swap at the root

a = p, b = qboth move to parentat null, jump to the other nodestop when a == bThe rule: a = a.parent or q, b = b.parent or p.a path: 5 → 3 → null → 1 → 3b path: 1 → 3 → null → 5 → 3both take 4 steps, meet at 3
Each pointer walks up; when it falls off the root it jumps to the other starting node. They meet at the LCA.
ComplexityTime O(n)Space O(1)Each pointer walks up at most the full height of the tree plus one redirect, so the total work is linear in the tree height, and only two pointers are stored.

What Trips People Up in Real Interviews

1

Clarify that each node has a parent pointer, unlike the standard binary tree LCA problem.

2

The hash set approach is the most intuitive: store p ancestors, walk q up until you hit a common node.

3

The two-pointer approach is elegant: if p and q are at different depths, the shorter path wraps around and the pointers meet at the LCA.

4

Key insight for two pointers: after pointer A reaches root, redirect to q. When pointer B reaches root, redirect to p. They will meet at the LCA.

5

Edge case: if p is an ancestor of q, the LCA is p. Both approaches handle this correctly.

Solution Code

O(n) time
class Solution:
    def lowestCommonAncestor(self, p: Node, q: Node) -> Node:
        a, b = p, q
        while a != b:
            a = a.parent if a.parent else q
            b = b.parent if b.parent else p
        return a

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 III problem?

Given a binary tree where each node has a parent pointer in addition to left and right children, find the lowest common ancestor of two nodes p and q. The parent pointer of the root is null. Both p and q are guaranteed to exist in the tree.

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

The optimal approach runs in O(n) time and O(1) 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 III?

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

What are common mistakes on Lowest Common Ancestor of a Binary Tree III?
  • Clarify that each node has a parent pointer, unlike the standard binary tree LCA problem.
  • The hash set approach is the most intuitive: store p ancestors, walk q up until you hit a common node.
  • The two-pointer approach is elegant: if p and q are at different depths, the shorter path wraps around and the pointers meet at the LCA.
  • Key insight for two pointers: after pointer A reaches root, redirect to q. When pointer B reaches root, redirect to p. They will meet at the LCA.
  • Edge case: if p is an ancestor of q, the LCA is p. Both approaches handle this correctly.