Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 16 Dec, 2020

Moderate

```
• 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.
```

```
'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.
```

```
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).
```

```
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
```

```
The only line contains the LCA of 'P' and 'Q'.
```

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*.

- If

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.

- If

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.

- If