Skip to main content
Talentd

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

MediumPremiumFree on FleetCodeHash TableTwo PointersTreeBinary Tree12 min readAsked at: Amazon, Microsoft, Apple +7
Practice this problem

Problem Statement

Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

Each node will have a reference to its parent node. The definition for Node is below:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a 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)."

 

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 since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

 

Constraints:

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

Approach Overview

Problem Overview: Given two nodes in a binary tree where each node has a pointer to its parent, return their lowest common ancestor (LCA). The LCA is the deepest node that has both nodes as descendants. Because parent pointers exist, you can traverse upward from any node instead of starting at the root.

Approach 1: Hash Table (O(h) time, O(h) space)

Start from node p and walk upward through its parent pointers while storing every visited node in a hash set. Then move upward from node q, checking at each step whether the node already exists in the set. The first match is the lowest common ancestor. The key insight: all ancestors of p form a path to the root, so the first ancestor of q that intersects this path must be the LCA. This approach relies on constant-time hash lookups and works for any binary tree structure. Time complexity is O(h), where h is the tree height, and space complexity is also O(h) due to the stored ancestors.

Approach 2: Two Pointers (O(h) time, O(1) space)

This approach treats the ancestor chains like two linked lists. Use two pointers starting at p and q. Move each pointer upward using the parent pointer. When a pointer reaches null, redirect it to the other node's starting position. Eventually both pointers traverse equal path lengths and meet at the LCA. The trick works because both pointers cover the combined depth of both nodes, similar to the classic intersection-of-linked-lists technique. Time complexity is O(h) and space complexity is O(1), making it the most space-efficient solution.

Both approaches rely on traversing parent pointers rather than exploring children from the root. That changes the typical tree traversal pattern and makes the problem closer to path intersection. The first solution uses a hash table to track visited ancestors, while the second uses a pointer-switching trick commonly seen in two pointers problems.

Recommended for interviews: The two-pointer approach is usually preferred because it achieves O(1) extra space while keeping the same O(h) time complexity. Still, explaining the hash set method first clearly demonstrates your reasoning: store one path, intersect with the other. Showing both approaches signals strong problem-solving depth.

Approach 1: Hash Table

We use a hash table vis to record all nodes on the path from node p to the root node. Then we start from node q and traverse towards the root node. If we encounter a node that exists in the hash table vis, then this node is the nearest common ancestor of p and q, and we can return it directly.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 2: Two Pointers

We can use two pointers a and b to point to nodes p and q respectively, and then traverse towards the root node. When a and b meet, it is the nearest common ancestor of p and q. Otherwise, if pointer a traverses to the root node, then we let it point to node q, and do the same for pointer b. In this way, when the two pointers meet, it is the nearest common ancestor of p and q.

The time complexity is O(n), where n is the number of nodes in the binary tree. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Hash Table—
Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Table (Ancestor Set)O(h)O(h)When you want a straightforward implementation and quick ancestor lookup
Two Pointers (Parent Traversal)O(h)O(1)Best general solution when minimizing extra memory is preferred

Video Solution

LOWEST COMMON ANCESTOR OF A BINARY TREE III [PYTHON] • Cracking FAANG • 22,224 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Lowest Common Ancestor of a Binary Tree III easy or hard?
The problem is rated Medium because it requires recognizing that parent pointers change the traversal strategy. Once you model ancestor paths like linked lists, the two-pointer solution becomes straightforward.
Lowest Common Ancestor of a Binary Tree III Python/Java solution
In Python or Java, the hash set solution stores ancestors of one node and checks the other node while traversing upward. The optimal solution uses two pointers moving through parent references until they meet. Both implementations run in O(h) time and are commonly used in coding interviews.
How to solve Lowest Common Ancestor of a Binary Tree III in O(n)?
Traverse ancestors using parent pointers instead of exploring the whole tree. One method stores all ancestors of node p in a hash set, then walks upward from node q until a match is found. Another method uses two pointers that switch starting nodes when reaching the root, guaranteeing an intersection at the LCA.
What is the best approach for Lowest Common Ancestor of a Binary Tree III?
The two-pointer approach is typically the best solution. Each pointer starts at one node and moves upward using parent pointers. When a pointer reaches null, it switches to the other node's starting position. Both pointers eventually meet at the lowest common ancestor with O(h) time and O(1) space.
Is Lowest Common Ancestor of a Binary Tree III asked at Google/Amazon/Meta?
Lowest Common Ancestor variations appear frequently in interviews at companies like Google, Amazon, Meta, and Microsoft. This version is common because the parent pointer changes the typical tree traversal strategy and tests understanding of pointer techniques.
What data structure is used in Lowest Common Ancestor of a Binary Tree III?
Common implementations use a hash set to store visited ancestors or a two-pointer technique similar to linked list intersection. The underlying structure is a binary tree with parent pointers, which allows upward traversal without starting from the root.
What is the time complexity of Lowest Common Ancestor of a Binary Tree III?
The optimal solutions run in O(h) time, where h is the height of the tree. Each pointer or traversal moves upward through ancestors until the lowest common ancestor is found. In the worst case, this is proportional to the depth of the nodes from the root.

Ready to solve this problem?

Practice Lowest Common Ancestor of a Binary Tree III 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