Whether you are a beginner or a professional coder, you must have knowledge of the binary search tree.
The Binary Search Tree is one of the important topics available in data structures. It comes with special properties where the left subtree stores an element that is less than the root node whereas the right subtree contains an element that is more than its parent node. Every node is connected with the help of some nodes which are known as the root nodes.
Those root nodes are known as the Lowest Common Ancestor of BST and are the common node between any two nodes.
There are a lot of programmers who are not able to find the LCA of BST. If you are also facing the same problem, then make sure to read the guide till the end.
What is the Lowest Common Ancestor of BST?
The Lowest Common Ancestor or LCA of BST is based on finding the lowest node which is the descendant between the two given nodes. It is important for you to understand it as the recruiter and most coding platforms ask for this problem.
As we have explained, the Binary Search Tree is divided into two parts which are the left subtree and the right subtree. You have to traverse over both of them along with the parent node to find the lowest common ancestor.
Even the name suggests that we have to find the minimum common element between the two nodes. For any given two nodes, we have to find the lowest minimum number which is making a connection between them. Now, let’s understand it properly with the help of examples.
Example 1
Find the LCA of BST of 10 and 14.
11
/ \
8 12
/ \ / \
4 13 10 14
/ \
3 16
Answer: 12 is the LCA of BST of 10 and 14.
Explanation: For the given nodes, the node that is close to it and descendant to it is 12. To find the LCA, we have to traverse over the given nodes. After traversing, we have to check for their parent node. After checking, we compare both to show the output.
Example 2
Find the LCA of BST of 10 and 14.
10
/ \
8 12
/ \ / \
4 13 11 14
/ \
3 16
Answer: 10 is the LCA of BST of 10 and 14.
Explanation: For the given nodes, the 10 is the LCA because we have to check for the parent node. In this case, the parent node is 10 itself, thus, we can’t compare it with any other node because there is no root node present for it. That’s why the 10 is the Lowest Common Ancestor of the BST of 10 and 14.
How To Solve The Lowest Common Ancestor Problem?
To find the lowest common ancestor of the binary search tree, you will need to traverse it. After traversing, you will need to compare it with the other given nodes. Once you are done with the comparison, then you will be able to print the element which you have got.
For doing all of these procedures, you will have to stick with the right approach. That’s why we are here with the right approach that will help you in finding the LCA of BST.
Let’s check it out.
Problem Statement
Find the LCA of BST for the given nodes: (10, 14) and (11, 14).
11
/ \
8 12
/ \ / \
4 13 10 14
/ \
3 16
Approach
For any given node, we have to start our traversal. Once we have started our traversal, then we will search for the given nodes.
After finding the given node, we will search for its parent node.
Once we have got the parent node, then we will compare it with the given nodes.
After the comparison, we will see whether it is the lowest of any of them or not.
If it is lower than the given node, then we have found the LCA.
We will print the LCA for that BST.
Through this, we hope that you have got a better understanding of what we are going to do with the problem. Now, let’s see the dry run to check how it works.
Dry Run
We will start our traversal on the BST. However, first of all, we will check for the nodes to find the right direction for traversing.
As the one node is 10, then we will compare it with the root node which is 11. Thus, the nodes that are lesser than the root node will be stored in the left subtree. Therefore, we will start traversing and checking for the nodes. However, on traversing, we have not found the node, then we will check another node which is 14. Node 14 is greater than 11, so it will be on the right subtree.
After it, we will start traversing over the right subtree. On traversing the first element that we will find is 12. Again, we will apply the same criteria for the search, then we will traverse over the right subtree. On traversing, we found node 14.
Now, we have to look for the 10. We will traverse over the left subtree of the 12 because it is greater than 10. On traversing over the left subtree, we will find node 10. Now, we will check for both parent nodes.
The result that we will get is 12. Therefore, node 12 is the LCA of BST of (10, 14).
By following the same way, we will do it for the next given nodes. For traversing, we will compare the nodes, the first node is 11 and it matches the root node, then we have to look for the other one which is 14. The 14 will be in the right subtree because it is greater than the 11.
Now, on traversing, we will find the 14. However, on checking for the parent node of both nodes, it is 11 itself. Thus, node 11 will be the answer for the LCA of BST of (11, 14).
After that, we will print the answer.
Conclusion
Through the help of the given approach and dry run, you will be able to solve the problem. Once you have solved the problem, then you can easily attempt the subarray with given sum. The problem of sum of subarray minimums is based on finding the contiguous part of the array which makes the total sum.
Write your code for the LCA of the BST problem to enhance your coding skills!
Comments