Last Updated: 16 Dec, 2020
LCA of Two Nodes In A BST
Moderate
Asked in companies
You are given a binary search tree of integers with N nodes. You are also given references to two nodes 'P' and 'Q' from this BST.
Your task is to find the lowest common ancestor(LCA) of these two given nodes.
The lowest common ancestor for two nodes P and Q is defined as the lowest node that has both P and Q as descendants (where we allow a node to be a descendant of itself)
A binary search tree (BST) is a binary tree data structure which has the following properties.
• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.
For example:
'P' = 1, 'Q' = 3
tree = 2 1 4 -1 -1 3 -1 -1 -1,
The BST corresponding will be-
Here, we can clearly see that LCA of node 1 and node 3 is 2.
Input Format:
The first line contains two space-separated integers, 'P' and 'Q', the nodes whose LCA we have to find.
The second line contains the elements of the BST in the level order form separated by a single space.
If any node does not have a left or right child, take -1 in its place. Refer to the example below.
Example:
Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.
For example, the input for the tree depicted in the below image would be :
1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1
Explanation :
Level 1 :
The root node of the tree is 1
Level 2 :
Left child of 1 = 2
Right child of 1 = 3
Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6
Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)
Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)
The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null (-1).
Note :
The above format was just to provide clarity on how the input is formed for a given tree.
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format :
The only line contains the LCA of 'P' and 'Q'.
Approaches
We will traverse the BST in a depth-first manner. The moment we encounter either of the nodes P or Q, we will return some boolean flag. The least common ancestor would then be the node for which both the subtree recursions return a ‘True’ flag value.
The algorithm will be -
- We will start traversing a BST from the root node in a recursive manner.
- Let the current node in each recursive call be ‘currNode’. In each recursive call, we will-
- If currNode is equal to P we increment ‘isTrue’ by 1.
- If currNode is equal to Q we increment ‘isTrue’ by 1.
- We will recurse over the left subtree and find the value of ‘isTrueLeft’.
- We will recurse over the right subtree and find the value of ‘isTrueRight’.
- If the value of (isTrue + isTrueLeft + isTrueRight) >= 2 then ‘currNode’ is the LCA.
- If (isTrue + isTrueLeft + isTrueRight) > 0, we return 1. Else, we return 0.
The lowest common ancestor of two nodes P and Q would be the last ancestor in terms of depth of the node, which is common to both the nodes. The key observation here is that for the LCA node, one of P or Q would be in the left subtree, and one would be in the right subtree.
The algorithm will be -
- We can use a recursive approach for finding out the LCA.
- Let the current node in each recursive call be ‘currNode’. In each recursive call, we will-
- If currNode -> data is less than P -> data and Q -> data, then LCA would be in the right subtree.
- If currNode -> data is greater than P -> data and Q -> data, then LCA would be in the left subtree.
- Else, currNode would be the LCA.
We can also use an iterative approach to find out the LCA of two nodes P and Q.
The algorithm will be -
- Let the current node in the iteration be ‘currNode’.
- While currNode is not equal to NULL:
- If currNode -> data is less than P -> data and Q -> data, then LCA would be in the right subtree.
- If currNode -> data is greater than P -> data and Q -> data, then LCA would be in the left subtree.
- Else, currNode would be the LCA.