Lowest Common Ancestor in the Binary Tree – Complete Guide

Trees are definitely one of the most common naturally occurring structures that we can see almost everywhere on this planet.

Inspired by these real-life structures (the outward branches of the trees), we have the concept of Binary Search Tree that is designed by developers to facilitate storing of data within these branches (or nodes as they call it in programming terms).

Now, every node within the Binary Tree gives birth to two child nodes which makes the former node the parent node of the two children nodes.

This is what we commonly refer to as the LCA (lowest common ancestor) or LCA of Binary Tree.

Allow us to share more about finding LCA or the Lowest Common Ancestor of a Binary Tree in this blog.

What Does It Mean By Lowest Common Ancestor Of A Tree?

Lowest Common Ancestor or LCA of a Binary Tree is essentially the common ancestor between two given nodes that share the same parent within the structure.

Refer to the following example to learn more about the LCA (lowest common ancestor) of the Binary Tree.

[ 1 ]

[ 2 ]. [ 3 ]

[ 4 ]. [ 5 ]. [ 6 ]. [ 7 ]

Now, as depicted in the above diagram of a Binary Search Tree, the nodes two and three have node one as their parent node. While, nodes 4 and 5 and nodes 6 and 7 have the nodes 2 and 3 as their parent nodes respectively.

Hence, in terms of finding lca of the Binary Tree that has been mentioned above, we can say that node 1 is the LCA (lowest common ancestor) of nodes 2 and 3, while node 2 is the LCA (lowest common ancestor) of nodes 4 and 5.

How To Figure Out the Lowest Common Ancestor (LCA) Of A Tree?

Did you know?

The LCA (lowest common ancestor) of the Binary Tree is used for finding out the distance between two different nodes within the structure of the tree!

Now, there are a number of different approaches and algorithms that can be used for figuring out the LCA (lowest common ancestor) of the Binary Tree.

We will definitely not be applying every single approach/algorithm that is available out there for finding lca of Binary Tree.

Some of the most resourceful algorithms are as follows:

Using the sorting algorithm
Using the Single Traversal method

Method 1: Using The Sorting Algorithm

The sorting algorithm in programming is essentially employed for shuffling the contents of a data in a specific order so that it becomes quite easier to navigate the entire data.

The sorting algorithm is more commonly used in the context of finding the second largest element in array. But in this instance, we will be applying this approach for finding the lowest common ancestor in a BST.

This algorithm sorts data into the following categories:

Alphabetical order

This can either be from A-Z or from Z-A. Both will essentially be in the alphabetical order regardless of the order of the characters.

Highest to the lowest value and vice versa

Now, the contents of the Binary Tree is not limited to a specific number value, meaning that a tree structure can hold an infinite number of data.

The general sorting would look something like this:

1- 100 or 100 – 1 (note that the sorting can either be in the ascending or the descending formats)

Shortest to longest distance

Well, this one is quite self-explanatory. The data contained within Binary Tree can also be sorted in terms of the shortest to the longest distance.

So, in the context of finding lca of Binary Tree the intention of using the sorting algorithm is to start storing the path from the first node i.e the root of the tree to nodes: n1 and n2 separately.

Next up, we will start traversing the entire paths but matching their elements simultaneously until we find the first mismatched element.

Here’s how the algorithm should work:

Start by finding a path from the first node i.e the root to the n1 node of the BST and store the value in an array.
Do the same with the second node i.e n2 and store the value in another array.
Keep traversing both the paths until you find a hint of the first mismatched element.
You can return all the common elements of the Binary Search Tree until the mismatched element.

Time Complexity for the problem:

The estimated time complexity for this problem would be O(N). This is because in the sorting algorithm, the tree has been traversed twice and then the paths have been compared.

Method 2: Using the algorithm for Single Traversal

If you are familiar with the Brute Force Algorithm, then it would be easier to understand the methos of traversals in a Binary Tree. This is because they use the common pattern of checking every item contained within the data structure individually.

These form of approaches are also effectively used for in the problems of fiding zero sum subarray or finding the second largest element in array.

The methods of in-order traversal, pre-order traversal and post-order traversal are the three approaches that relate to single traversal.

Let us briefly discuss these approaches before learning how to apply these algorithms:

In-order traversal

Within the in-order traversal approach, the algorithm starts traversing from the left part of the Binary Tree i.e the left sub-tree further moves to the right part also known as the right sub-tree.

Pre-order traversal

This algorithm startsfrom the first node i.e the root of the given Binary Search Tree and moves along to the left sub-tree finally, to the right sub-tree.

Post-order Traversal

Exactly opposite to the pre-order traversal, the post-order traversal starts from the left part of the Binary Search Tree and moves along to the right part. Finally, the algorithm will visit the root of the tree as the last part of its traversal.

Now, in the context of finding LCA of Binary Tree, the single order traversal algorithms can be applied as follows:

The idea here is to start traversing the tree from the first node i.e the root itself. If the values of the n1 and the n2 nodes match identically with the root then, we can conclude that the root is the LCA (lowest common ancestor).
This is because the value of the Lowest Common Ancestor of a Binary Tree is always equivalent to the value of its two children nodes.
In case the root appears to be non-identical, we shall move forward to the left part of the Binary Search Tree and try to match the elements and so forth!
If the LCA is not found by the left subtree, we can finally visit the right subtree.

Here’s how the algorithm for this should work:

Startfrom the first node i.e the root and go ahead with matching the values.
Return the values as NULL if no resemblance is found or, in case you find any resemblance, return the value of the root.
Perform the same function with the left subtree.
If the LCA is still absent, move over to the right subtree.
The part of the Binary Search Tree that returns a NON-NULL value consists of the LCA.

Wrapping Up

Binary Search Trees in Data Structures are more complex versions of storing data than the other forms such as the arrays.

If interested, you can check out different array topics covered in our blogs such as finding triple sum arrays or finding the second largest element in an array.

Post Views: 440

You may also like: