Scaler
Academy
Data Science
Neovarsity
New
Skill Test
CoursesFree Masterclass
Search for Articles, Topics
Lowest Common Ancestor of a Binary Tree

Lowest Common Ancestor of a Binary Tree

By Paras Yadav
9 mins read
Last updated: 10 Oct 2023
437 views
Learn via video course
FREE
View all courses
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Start Learning
Start Learning View all courses
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Start Learning
Topics Covered

Problem Statement

Given a binary tree, and two values v1 and v2, find the lowest common ancestor of nodes with their values as v1 and v2.

Where the lowest common ancestor of two nodes (Node1 and Node2) is the deepest node of which Node1 and Node2 are descendants. Note that here we consider that a node is the descendant of itself also.

Examples

Example 1 -

Input - Given Tree -

LCA Queries -

  • LCA (4, 5)
  • LCA (7, 4)
  • LCA (5, 8)

Output -

Explanation - By seeing the tree structure we can see that -

  • 2 is the deepest node in the tree whose descendant nodes are 4 and 5.
  • 4 is the deepest node in the tree whose descendant nodes are 7 and 4.
  • 1 is the deepest node in the tree whose descendant nodes are 5 and 8.

Example 2 -

Input - Given Tree -

LCA Queries -

  • LCA (4, 2)
  • LCA (4, 5)

Output -

Explanation - By seeing the tree structure we can see that -

  • 2 is the deepest node in the tree whose descendant nodes are 4 and 2.
  • 3 is the deepest node in the tree whose descendant nodes are 4 and 5.

Constraints

  • 0<n<1050 < n < 10^5, where nn is the number of nodes.
  • 0<node.val<1090 < \text{node.val} < 10^9

Approach 1: By Storing Root To n1 And Root To n2 Paths

In any tree structure there exists a unique path between any two nodes. Therefore there must exist a unique path from the root to node n1 and n2. Also, there will be some common nodes in both paths because we are starting from the root node.

Algorithm

To find the lowest common ancestor of a binary tree we will perform the following steps -

  • Store the path from the root to n1 in a list, let it be path1.
  • Store the path from the root to n2 in a list, let it be path2.
  • Traverse in both the obtained paths till nodes are common and return the node that occurs just before the mismatch.

Now let's see how we can find the path from the root to the target -

  • Define an empty list of integers (say path) and pass it to a boolean type recursive function findPath that accepts three arguments i.e.i.e. root, val, and path.
  • If the root is null then return false.
  • Push root.val in the path list.
  • Now, if root.val is equal to val then return true as we've found the desired node.
  • Then if on recurring on the left and right subtree we find our desired node in any of the subtree return true.
  • Now to backtrack, remove the element at the last position in our path list.
  • At last, if nothing worked out then return false.

Dry Run

Let's dry run this approach to find the LCA of a binary tree shown below - Given Tree -

  • Query 1 - LCA (4, 5)
    • Find the path from the root node to the node with value 4. path1 = [1→2→4][1\rightarrow 2 \rightarrow 4]
    • Find the path from the root node to the node with value 5. path2 = [1→2→5][1\rightarrow 2 \rightarrow 5]
    • Now, we traverse both the lists till the path is the same (the value of nodes in the path is the same in both lists). Therefore at the 2nd2^nd index (0-based), we found a mismatch, and hence we will return the value just before the 2nd2^{nd} index i.e.i.e. 2.
  • Query 2 - LCA (7, 4)
    • Find the path from the root node to the node with value 7. path1 = [1→2→4→7][1\rightarrow 2 \rightarrow 4 \rightarrow 7]
    • Find the path from the root node to node with value 4. path2 = [1→2→4][1\rightarrow 2 \rightarrow 4]
    • Now, we traverse in both the lists till the path is same (value of nodes in the path is same). Here, we will reach the last index of path1 and do not find any mismatch therefore we will return the node at the last index of path1.
  • Query 3 - LCA (5, 8)
    • Find the path from the root node to the node with value 5. path1 = [1→2→4][1\rightarrow 2 \rightarrow 4]
    • Find the path from the root node to the node with value 8. path2 = [1→3→7→8][1\rightarrow 3 \rightarrow 7 \rightarrow 8]
    • Now, we traverse in both the lists till the path is the same (value of nodes in the path is the same). At the 1st1^{st} index, we encounter a mismatch in paths so we will return the node present at the 0th0^{th} index i.e.i.e. 1.

Java Implementation

Output -

C++ Implementation

Output -

Python

Output -

Complexity Analysis

  • Time Complexity - To get root to target path we need to traverse the whole binary tree, which costs O(n)O(n) time, where nn is the number of nodes present in the tree. Therefore, it requires O(n)O(n) time to find LCA of a binary tree.
  • Space Complexity - The height of the recursive tree can reach up to O(h)O(h), also in the worst case (target node is the deepest leaf), the size of the path list will be O(h)O(h) where hh is the height of the binary tree. Hence, the overall space complexity is O(h)O(h).

Approach 2 - Using Single Traversal (Recursive Approach)

In the previous approach, it requires traversing the tree two times (once to find the path from the root node to 1st1^{st} target node and from the root node to the 2nd2^{nd} target node). But we can optimize our approach such that it requires only a single traversal to find the lowest common ancestor of a binary tree.

The idea is to traverse the tree starting from the root. If the node's value does not match with any of the target key i.e.i.e. n1 or n2 we recur for both the left and the right subtree. Else if the left subtree contains one key and the right subtree contains one key then the node is the LCA of a binary tree. Otherwise, if the left subtree contains both the keys then LCA is present in the left sub-tree, else it is present in the right subtree.

Algorithm

The steps required in the algorithm to find LCA of a binary tree as follows -

  • Define two boolean values (say b1 and b2) which will help us to verify that both keys provided as the input exists in a binary tree or not.
  • Define a Node type recursive function findLCA that accepts three arguments i.e.i.e. node, n1, and n2.
    • Define a base condition that returns null whenever the node is null.
    • Define a variable ans and initialize it to be null.
    • Check if node.val is equal to n1, make b1 to be true, and assign the node to ans.
    • Otherwise, check if node.val is equal to n2, make b2 to be true, and assign the node to ans.
    • Now, recurse for the left and the right subtree and store their return value in variables (say leftAns and rightAns).
    • If we have found that ans is no longer equal to null then we will return it.
    • Otherwise, if we found that both the leftAns and rightAns are not null then we will return the node.
    • At last, we will check if leftAns is not null then we will return leftAns otherwise we will return rightAns.
  • Now we will check if both the values b1 and b2 are true or not. If they both are true we will return the value of the node returned by the recursive function. Otherwise, we will return -1.

Java Implementation

Output -

C++ Implementation

Output -

Python Implementation

Output -

Complexity Analysis

  • Time Complexity - Since we will be traversing the whole binary tree in the worst case. Therefore, it requires O(n)O(n) time to find LCA of a binary tree.
  • Space Complexity - The height of the recursive tree can reach up to O(h)O(h), where hh is the height of the binary tree. Hence, the overall space complexity is O(h)O(h).

Approach 3 - Iterative Approach

In our last approach, we've seen how we can store the paths from the root node to the target nodes and use them to find the lowest common ancestor. Here, we will see how we can find the lowest common ancestor of the binary tree using an iterative method. The main idea is to traverse the tree until we have found both of our target nodes and then we will traverse back from the target node to the root node using the Map data structure.

Let's see the steps involved in the algorithm -

  • Define a HashMap in which both the key and value are of the node type.
  • Also declare a Queue of Node type which will be used to traverse the in level-order fashion.
  • Then traverse in level order till we haven't found both of our target nodes. Also, while traversing we will make sure that we map the nodes with their parents using the Map we declared initially.
  • Now we will move from target1 to the root node and store the path in a HashSet.
  • Then, we will move from target2 to the root node until the nodes in the path are not present in the HashSet.
  • The very first node that is part of the path from target2 to the root node and is present in the HashSet is our answer.

Java Implementation

Output -

C++ Implementation

Output -

Python Implementation

Output -

Complexity Analysis

Time Complexity - We need to traverse the whole tree in the worst case which costs O(n)O(n) time. Hence, the overall time complexity to find LCA of a binary tree is O(n)O(n). Space Complexity - To traverse the binary tree in a level order fashion, the size of the queue can reach up to O(n)O(n). Hence, the overall space complexity is O(n)O(n).

Conclusion

  • The lowest common ancestor (LCA) of two nodes in a binary tree is the deepest node which is the ancestor of both the nodes.
  • Lowest common ancestor can be found by storing paths from the root node to the target nodes and the finding the last common node in the path. Which requires O(n)O(n) time.
  • LCA can easily be found by traversing the binary tree once, and finding the positions of the target nodes. Which again requires O(n)O(n) time, but only a single traversal of tree is needed.
  • It is very much used practically also, for example, to find the directory inside which two or more given directories are present.