Skip to main content
Talentd

Lowest Common Ancestor of a Binary Tree - Solution & Explanation

MediumTreeDepth-First SearchBinary Tree22 min readAsked at: Amazon, Microsoft, Apple +19
Practice this problem

Problem Statement

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T 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 will exist in the tree.

Approach Overview

Problem Overview: Given the root of a binary tree and two nodes p and q, return their lowest common ancestor (LCA). The LCA is the lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself).

Approach 1: Path to Root Approach (O(n) time, O(n) space)

This approach records the path from the root to each target node. Run a DFS to build a list of nodes from the root to p, then repeat for q. Once both paths are available, iterate through them from the start and find the last common node before the paths diverge. That node is the lowest common ancestor. The tree traversal takes O(n) time in the worst case, and storing both paths requires O(n) extra space.

The method is easy to reason about because it converts the problem into comparing two arrays of ancestors. It works well when you want a clear conceptual model of ancestor relationships. The downside is the extra memory used to store both paths.

Approach 2: Recursive Depth-First Search (O(n) time, O(h) space)

This is the standard optimal solution. Traverse the tree using recursive DFS. If the current node is null, return null. If the current node matches p or q, return that node. Recursively search the left and right subtrees. If both recursive calls return non-null values, the current node is the first point where the two targets split across subtrees, making it the lowest common ancestor.

If only one side returns a node, propagate that result upward. Eventually the recursion bubbles the correct ancestor back to the root call. Each node is visited once, giving O(n) time complexity. The recursion stack consumes O(h) space where h is the tree height.

This approach works naturally with Tree recursion patterns and is commonly used in Depth-First Search problems. Since binary tree traversal is already required, the solution stays simple and avoids storing full paths.

Recommended for interviews: The recursive DFS solution is what interviewers typically expect. It demonstrates strong understanding of Binary Tree traversal and recursive reasoning. Mentioning the path-to-root approach first shows you understand the problem structure, but implementing the DFS solution proves you can optimize both memory usage and code simplicity.

Approach 1: Recursive Depth-First Search

This approach uses recursion to traverse the tree starting from the root. If the current node is either p or q, then the node is returned upwards in the recursion stack as the potential LCA. Otherwise, we continue to search both left and right subtrees. If both subtrees return non-null values, it means p and q are in different subtrees, and the current node is the LCA. If only one subtree returns a non-null value, it means both nodes are located in that subtree and that subtree's root should be the LCA.

This C code defines a recursive function to find the LCA of two nodes in a binary tree. It checks if the current node is NULL or matches either of the two nodes p or q and returns the node if true. It then recursively checks the left and right children. If both are non-null, the current node is the LCA; otherwise, it returns the non-null child.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N), where N is the number of nodes in the binary tree, as we visit each node only once.
Space Complexity: O(N) due to the recursion stack when the tree is completely unbalanced.

Try this approach in the editor →

Approach 2: Path to Root Approach

The basic idea is to find the paths from the root to the two nodes p and q. Once you have the paths, compare them to find the deepest common node. This method is straightforward, using known operations to reconfirm ancestor status along determined paths.

In C, we maintain arrays to keep track of paths from the root to the target nodes and compare these paths to find their last common node.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N) due to double traversal in finding paths for each node.
Space Complexity: O(H), where H is the height of the tree for storing path information.

Try this approach in the editor →

Approach 3: Recursion

We recursively traverse the binary tree:

If the current node is null or equals to p or q, then we return the current node;

Otherwise, we recursively traverse the left and right subtrees, and record the returned results as left and right. If both left and right are not null, it means that p and q are in the left and right subtrees respectively, so the current node is the nearest common ancestor; If only one of left and right is not null, we return the one that is not null.

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++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Depth-First Search

Time Complexity: O(N), where N is the number of nodes in the binary tree, as we visit each node only once.
Space Complexity: O(N) due to the recursion stack when the tree is completely unbalanced.

Path to Root Approach

Time Complexity: O(N) due to double traversal in finding paths for each node.
Space Complexity: O(H), where H is the height of the tree for storing path information.

Recursion—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Path to Root ApproachO(n)O(n)Useful for understanding ancestor relationships or when explicit root-to-node paths are required.
Recursive Depth-First SearchO(n)O(h)Best general solution for binary trees. Minimal extra memory and standard interview approach.

Video Solution

LOWEST COMMON ANCESTOR OF A BINARY TREE I | PYTHON | LEETCODE 236 • Cracking FAANG • 70,618 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Lowest Common Ancestor of a Binary Tree easy or hard?
Lowest Common Ancestor of a Binary Tree is generally classified as a Medium difficulty problem. The recursion logic is simple once you understand how subtree results propagate upward, but recognizing the split-point insight can take practice.
Lowest Common Ancestor of a Binary Tree Python/Java solution
Most implementations use recursive DFS in Python, Java, C++, or JavaScript. The function checks whether p or q exists in the left or right subtree and returns the current node when both sides contain one target node each.
How to solve Lowest Common Ancestor of a Binary Tree in O(n)?
Run a recursive DFS from the root. If the current node equals p or q, return it. Recursively search the left and right subtrees. When both sides return non-null values, the current node is the lowest common ancestor. Each node is processed once, giving O(n) time complexity.
What is the best approach for Lowest Common Ancestor of a Binary Tree?
The recursive Depth-First Search approach is considered the best solution. It traverses the tree once and determines the split point where nodes p and q appear in different subtrees. This method runs in O(n) time and uses O(h) space for the recursion stack, where h is the tree height.
Is Lowest Common Ancestor of a Binary Tree asked at Google/Amazon/Meta?
Lowest Common Ancestor is a classic tree interview question and appears frequently at companies like Google, Amazon, Meta, and Microsoft. Variants also appear in system design and advanced tree problems, making it a foundational concept for technical interviews.
What data structure is used in Lowest Common Ancestor of a Binary Tree?
The problem primarily uses a binary tree data structure combined with Depth-First Search traversal. Some alternative solutions also store root-to-node paths using arrays or lists to compare ancestors.
What is the time complexity of Lowest Common Ancestor of a Binary Tree?
The standard solution runs in O(n) time because each node in the binary tree may be visited once during the DFS traversal. Space complexity is O(h) due to the recursion stack, where h represents the height of the tree.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Cycle Length Queries in a Tree

Next

Find Players With Zero or One Losses