Max element in the path

Easy
0/40
Average time to solve is 15m
profile
Contributed by
18 upvotes
Asked in company
Amazon

Problem statement

Given a Binary Search Tree and two integers NODE1 and NODE2. You have to find the maximum element in the path from NODE1 to NODE2.

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

Note:

1. The path from NODE1 to NODE2 does not include NODE1 and NODE2.

2. NODE1 and NODE2 are unique.

3. If there is no element in the path from NODE1 to NODE2, return -1.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

Each test case follows:
The first line of every test case contains elements 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.

The second line contains two space-separated integers denoting NODE1 and NODE2.

For example, the input for the tree depicted in the below image would be :

example

20
10 35 
5 15 30 42 
-1 13 -1 -1 -1 -1 -1 
-1 -1

Explanation:

Level 1 :
The root node of the tree is 20
Level 2 :
Left child of 20 = 10
Right child of 20 = 35
Level 3 :
Left child of 10 = 5
Right child of 10 = 15
Left child of 35 = 30
Right child of 35 = 42
Level 4 :
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 15 = 13
Right child of 15 = null (-1)
Left child of 30 = null (-1)
Right child of 30 = null (-1)
Left child of 42 = null (-1)
Right child of 42 = null (-1)
Level 5 :
Left child of 13 = null (-1)
Right child of 13 = 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:
20 10 35 5 15 30 42 -1 13 -1 -1 -1 -1 -1 -1 -1
Output Format 
For each test case, print a single line containing a single integer denoting the maximum element in the path from NODE1 to NODE2. If either NODE1 or NODE2 does not exist in the BST, return -1.

The output of each test case will be printed in a separate line.
Note 
You don’t have to print anything; it has already been taken care of. Just complete the function.
Constraints 
1 <= T <= 100
1 <= N <= 3000
0 <= DATA <= 10 ^ 9
1 <= NODE1, NODE2 <= 10 ^ 9 

Where ‘T’ is the total number of test cases, 'N' denotes the number of nodes in the given BST,  'DATA' denotes the value of each node in the given tree, and NODE1 and NODE2 are 2 integers.

Time limit: 1 sec.
Sample Input 1:
1
5 3 7 1 4 6 9 -1 2 -1 -1 -1 -1 -1 -1 -1 -1
1 9
Sample Output 1:
7
Explanation of sample input 1:
The BST of the given elements is shown below.

example

The path from 1 to 9 is shown in the curve. 
As we can see, the maximum element in the path from 1 to 9 is 7.
Sample Input 2:
2
2 1 4 -1 -1 3 -1 -1 -1
3 5
7 5 8 -1 6 -1 10 -1 -1 9 -1 -1 -1
6 7
Sample Output 2:
-1 
5
Explanation of sample input 2:
Test case 1:
As 5 does not exist in the BST, simply return -1.

Test case 2:
After creating the BST for the given level order, we can see that the 5 is the maximum element between 6 and 7.
Hint

Try solving using LCA, lowest common ancestor. Can you do this without storing the paths?

Approaches (1)
Using LCA

We have to check that A and B exist in the BST. If any of them or both of them does not exist, simply return -1. 

For finding the maximum element in the path from A to B, we will traverse every node in this path to keep track of the maximum element.

We can find the path by finding the LCA of node1 and node2. LCA is the lowest common ancestor of node1 and node2. 

After finding the LCA, we will go from LCA to node1 and LCA to node2 and keep track of the maximum element in the path.

 

Algorithm: 

  • Check if both node1 and node2 exist in the BST or not. If yes, continue else return -1.
  • Find LCA, lowest common ancestor of node1 and node2.
  • Initialise a variable ‘maxElement’ by -1, in case there is no element in the path from node1 to node2.
  • Now, traverse the tree from LCA to node1 and keep updating the ‘maxElement’ such that if the current value is greater than ‘maxElement’, the current value will become ‘maxElement’.
  • Similarly, traverse the tree from LCA to node2 and keep updating the ‘maxElement’.
  • Return the ‘maxElement’.

 

Algorithm to check whether a node is present in the BST or not:  

  1. We will create a recursive function which takes the root of the BST and the value to be searched as arguments.
  2. Start from the root node.
  3. Compare the value of the node to the current value, i.e the value of the root.
    1. If they are equal, we will return true.
    2. If the value of the node is less than the current value, we will recursively check in the left subtree.
    3. If the value of the node is greater than the current value, we will recursively check in the right value.
  4. If we have traversed the tree completely, and we did not find the value, we will return false.

 

Algorithm to find the LCA, lowest common ancestor of two nodes in a BST:

While traversing the tree from top to bottom, the first node that which lies between the two nodes is the LCA.

  1. We will create a recursive function, which takes the root of the BST and two values node1 and node2.
  2. Start from the root node.
  3. Compare the value of the current node to the value of node1 and node2.
    1. If the value of the current node is less than the value of both node1 and node2, means both node1 and node2 lie in the right subtree. We will recursively call the function for the right subtree.
    2. If the value of the node is greater than the value of both node1 and node2, means both node1 and node2 lie in the left subtree. We will recursively call the function for the left subtree.
    3. If both the above cases are false, then return the current node as the LCA.
Time Complexity

O(H), where ‘H’ is the height of the BST.

 

Finding LCA and then traversing from LCA to root takes O(H) time.

In the worst case, the height of the tree could be the number of nodes in the tree. In that case, time complexity would be O(N).

Space Complexity

O(H), where ‘H’ is the height of the BST. 

 

O(H) recursion stack space is used by the algorithm. In the worst case, H will become N. Thus, space complexity is O(N) where N is the number of nodes in the BST.

Code Solution
(100% EXP penalty)
Max element in the path
Full screen
Console