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.

Description Solution Video 12:48

236. Lowest Common Ancestor of a Binary Tree

Medium70.1% acceptance22 companies

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, 10⁵].
-10⁹ <= Node.val <= 10⁹
All Node.val are unique.
p != q
p and q will exist in the tree.

Asked at top 20 of 22 companies

Newsbreak Meta Wix SAP Lucid Amazon Atlassian BitGo Tiktok Oracle Apple LinkedIn

+8 more

Adobe Yandex MongoDB Intel Microsoft Bloomberg Intuit

Google

Topics

12:48

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

Similar problems

Lowest Common Ancestor of a Binary Search TreeMedium Smallest Common RegionMedium Find Players With Zero or One LossesMedium Lowest Common Ancestor of a Binary Tree IIMedium Lowest Common Ancestor of a Binary Tree IIIMedium Lowest Common Ancestor of a Binary Tree IVMedium Step-By-Step Directions From a Binary Tree Node to AnotherMedium Cycle Length Queries in a TreeHard

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, x):
4#         self.val = x
5#         self.left = None
6#         self.right = None
7 
8class Solution:
9    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
10        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[3,5,1,6,2,0,8,null,null,7,4]
5
1

Input

[3,5,1,6,2,0,8,null,null,7,4]
5
4

Input

[1,2]
1
2

Your code is saved on this device.Solution