Lowest Common Ancestor of Binary Tree

mediumFREETrees & BFS/DFSMeta DSA

Given a binary tree (as a level-order array) and two node values p and q, find their lowest common ancestor (LCA).

The LCA is the deepest node that has both p and q as descendants (a node can be a descendant of itself).

Output the value of the LCA.

Example

Input

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

Output

Reasoning

The binary tree is constructed from the level-order array: 3,5,1,6,2,0,8,null,null,7,4, resulting in the following tree structure: 3 /
5 1 / \ /
6 2 0 8 /
7 4
The nodes with values p = 5 and q = 1 are identified in the tree.
We find the lowest common ancestor by moving up from p and q until we find a common node, which is the root node 3 in this case.
Since 3 is the deepest node that has both 5 and 1 as descendants, its value is the output: $3$ .

Constraints

2 <= number of nodes <= 10^5
All node values are unique
p != q
Both p and q exist in the tree

Learn this in

Depth First Search & TreesDSA Study Plan

More from Meta DSA

Valid Palindrome IIeasy Dot Product of Two Sparse Vectorseasy Random Pick with Weightmedium Copy List with Random Pointermedium Remove Nth Node From Endmedium

Concept primer

Background Knowledge

The Lowest Common Ancestor (LCA) problem is a fundamental concept in graph theory and tree data structures. In the context of a binary tree, the LCA of two nodes is the deepest node that has both nodes as descendants. This problem requires a good understanding of tree traversal techniques, such as Depth-First Search (DFS) and Breadth-First Search (BFS). Additionally, it's essential to grasp the concept of ancestors and descendants in a tree, where an ancestor of a node is a node that has a path to the given node, and a descendant is a node that has a path from the given node.

To approach this problem, it's crucial to understand the properties of a binary tree, including the parent-child relationship between nodes. In a binary tree, each node has at most two children (left child and right child), and each node has exactly one parent, except for the root node, which has no parent. This structure allows for efficient traversal and searching of nodes. The problem also involves finding the deepest node that satisfies the condition, which implies that we need to consider the height or depth of the nodes in the tree.

The given problem provides the binary tree as a level-order array, which represents the tree nodes in a breadth-first manner. This means that the array is filled level by level, from left to right, starting from the root node. Understanding this representation is vital to reconstructing the binary tree and solving the LCA problem.

Algorithm/Approach

The general approach to solving the LCA problem involves traversing the binary tree to find the nodes p and q, and then finding the common ancestor of these nodes. This can be achieved using various techniques, such as recursive DFS or iterative BFS. The key idea is to explore the tree, keeping track of the ancestors of each node, until we find the common ancestor of p and q. Another approach is to use a bottom-up strategy, where we start from the nodes p and q and move upwards to find their common ancestor.

Step-by-Step Strategy

To solve the LCA problem, follow these steps:

Reconstruct the binary tree from the given level-order array.
Find the nodes p and q in the tree.
Traverse the tree to find the ancestors of p and q.
Identify the common ancestor of p and q by comparing their ancestor paths.
Return the value of the LCA node.

Common Pitfalls

When implementing the solution, watch out for the following:

Incorrectly reconstructing the binary tree from the level-order array.
Failing to handle edge cases, such as when p or q is the root node.
Not considering the uniqueness of the LCA node, which may lead to incorrect results.
Inefficiently traversing the tree, resulting in high time complexity.

Time & Space Complexity

The expected time complexity for the LCA problem is O(n), where n is the number of nodes in the tree, since we need to traverse the tree to find the nodes p and q and their common ancestor. The space complexity depends on the approach used, but it can be O(h), where h is the height of the tree, for recursive solutions, or O(n) for iterative solutions that store the ancestor paths.

solution.py

Python 3.13

Test results