Lowest Common Ancestor in a Binary Tree

The binary tree concept may seem easier but the truth is, it is one of the extensive topics of programming.

The concept is used widely in real-life applications, making it an essential topic for any programmer.

Even in interviews at leading companies like Facebook, Amazon and Adobe, questions related to binary trees are often asked.

One such question related to the concept that you can’t miss is how to find the lowest common ancestor in a binary tree.

In this problem, you will have to find the node which has all the nodes as its descendants.

Do not worry if the problem confuses you! Scroll down and equip yourself with all the information you are required to know about the LCA of binary tree.

But the first thing to learn is the basics! So, let’s understand what the problem is!

Understanding Binary Tree

As the name suggests, a binary tree has a data structure like a tree having nodes and a root. The catch here is that a node can only have two child nodes or less than two. No parent node can have more than two children.

There is only one root node in the tree and two child nodes which can further have child nodes.

To understand better, consider the following example:

/ \

2 3

/ \ |

4 5 6

Here, 1 has two children nodes 2 and 3. Also, 2 have two children node whereas, node 3 has one child node.

Understanding The Problem Statement

In this problem, you will be provided with two nodes of the binary tree and you will have to write a code to determine the LCA of BST.

The lowest common ancestor of the given nodes is the one that has both nodes as its descendants. You can also call it a shared ancestor of nodes 1 and 2 which are located far from the root of the tree.

To understand better, consider the following example:

/ \

2 3

/ \ / \

4 5 6 7

You are given the following input:

Node 1: 4

Node 2: 5

The output of this program will be 2

The ancestors of 4 and 5 will be 1 and 2. Now, according to the lowest common ancestor problem, we need the lowest ancestor.

Therefore, we will choose 2.

Things to Remember While Finding LCA of a binary tree

While writing a code to find the lowest ancestor of a binary tree, you will have to keep the following things in mind:

All the nodes of the given binary tree are unique.
The values of nodes 1 and 2 are different and must be present in the binary tree.
To resolve the problem, you can choose to use additional memory, make use of helper functions and can make changes to the node structures. However, you are not allowed to add any parent pointer in the tree.

Methods To Find LCA of BST

There are two possible methods to find the lowest common ancestor of the given binary tree.

Recursive method
Iterative method

Recursive Approach

The recursive method is the first method that comes to the mind of people when it comes to traversing the tree in the depth-first method. While traversing the tree, whenever you will find any of the given nodes, you will have to return that node.

In this case, the lowest common ancestor will be the node for which the subtree recursions will print a non-empty node. There are chances that the subtree may print one of the given nodes only.

Steps to follow:

Begin with traversing the tree from its root node.
In case the present node is itself one of the given nodes, the program will print that node.
In case the right or left subtree returns a non-empty node, it implies that one of these nodes was found in the tree.
Lastly, if at any point of the traversal, the subtrees return a node, it implies that the LCA of BST is found for both nodes.

Complexity Analysis

Time Complexity: The time complexity of this method is calculated as O(n). Here, n represents the number of nodes present in the tree.
Space Complexity: The space complexity is calculated as O(n).

Iterative Approach

The main idea behind the iterative approach is that if there are parent pointers present for each given node, traversing back from the nodes can help you reach their ancestors. The first common node that we will come across in this tree will be the LCA of the BST given.

Therefore, you need to store the parent pointer in the dictionary when you traverse the tree. In this way, when you will find a common node in both dictionaries, you will be able to find the common ancestor.

Steps to Follow:

Start traversing the tree from its root node.
Keep traversing the tree until you find the given nodes. Meanwhile, you need to store the parent pointers in the dictionary.
When you will find both nodes, get all the ancestors for the first node and then store them in a set named ancestors.
In the same way, you will have to traverse the tree to find the ancestors of node 2. In case the ancestor of node 2 is present in the set of ancestors of node 1, it implies that it is the very first common ancestor between the nodes. Therefore, it will be considered the Lowest common ancestor of the given nodes.

Complexity Analysis

Time Complexity: In this method as well, the time complexity is calculated as O(n).
Space Complexity: The space complexity in this method is calculated as O(n). The worst-case scenario in this method is when the stack utilises the space of n and the values of the parent pointer and ancestor set are equal to n. Here, n denotes the height of the tree.

Conclusion

The lowest common ancestor problem is one of the advanced and medium-level problems that you may be asked to resolve.

To find the LCA of binary tree, you can either use a recursive approach or an iterative approach.

The time complexity in both methods is similar but there can be differences in space complexity.

Therefore, when choosing an optimal solution to resolve the problem, make sure to emphasise complexities and then choose a method.