Maximum value node

Easy
0/40
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
ArcesiumAccoliteArgano

Problem statement

Given a BST (Binary search tree) with N number of distinct nodes and two nodes ‘X’ and ‘Y’ (which are definitely present in the input BST). You need to find the value of the maximum node that lies in between the nodes ‘X’ and ‘Y’ (both inclusive) in the given BST.

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.

Note:

1. All the elements of the Binary Search Tree are unique.

2. You can’t use the same node value/element of BST twice.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer ‘T’, which denotes the number of test cases. Then each test case follows. 

The first line of every test case contains elements of the Binary Search Tree 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 of each test case contains two integers denoting the value of nodes ‘X’ and ‘Y’.

For example:

The input for the tree depicted in the below image would be :

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

For each test case, print a single integer denoting the value of maximum node lies between ‘X’ and ‘Y’.

Note:

You don’t need to print the output, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5    
1 <= N <= 10 ^ 3
0 <= DATA <= 10 ^ 6
1 <= X, Y <= 10 ^ 6 

Where ‘DATA’ denotes the value of each node in the given tree.
‘N’ denotes the number of nodes in BST.

Time limit: 1 sec
Sample Input 1:
2 
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
2 10
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
8 7
Sample Output 1:
10
8
Explanation for sample input 1:

For the first test case, the maximum value of node lying between 2 and 10 is 10    

For the second test case, the maximum value of nodes lying between 8 and 7 is 8.
Sample Input 2 :
2
7 3 10 1 5 9 -1 -1 -1 -1 6 -1 -1 -1 -1
3 9
7 3 10 1 5 9 -1 -1 -1 -1 6 -1 -1 -1 -1
1 6
Sample Output 2:
10
6
Hint

Think of the solution using the Lowest Common Ancestor of the two given nodes.

Approaches (1)
Lowest Common Ancestor

The idea is to find the Lowest Common Ancestor of node ‘X’ and node ‘Y’. Then search for the maximum node between LCA and ‘X’, also find the maximum node between LCA and ‘Y’. The answer will be a maximum node of two.

 

Approach :

 

  • First, find the Lowest Common Ancestor of the two nodes ‘X’ and ‘Y’, and store the result node in the node variable, say ‘ancestor’.
  • Now calculate the maximum value between ‘ancestor’ and ‘X’ and then between ‘ancestor’ and ‘Y’ and return the maximum of both.

 

Description of solve ('ancestor', ‘value’) function:

 

  • To calculate the maximum value between ‘ancestor’ and the node, let's define a function, say ‘solve()’ taking ‘ancestor’ and ‘value’ as arguments.
    • Take a node ‘temp’ pointing to ‘ancestor’ and an integer variable ‘mx’ initialized with ‘INT_MIN’ to store the maximum result.
    • Iterate ‘temp’ until ‘temp → data’ is not equal to ‘value’.
      • If ‘temp → data' is less than ‘value’, update ‘mx’ with a maximum value of ‘mx’ and ‘temp → data'.
      • Shift ‘temp’ to ‘temp → left'.
      • Else update ‘mx’ with a maximum value of ‘mx’ and ‘temp → data' and shift ‘temp' to ‘temp →  right’
  • Return the maximum of ‘mx’ and ‘value’.
Time Complexity

O(N), where ‘N’ denotes the height of the BST.

 

As both the operations of finding LCA and then find the maximum value between the LCA and the given nodes takes O(N) for the worst-case i.e. for the skewed tree each making search operations as O(2 * N). Therefore, the overall time complexity will be O(N).

Space Complexity

O(1)

 

As constant space is used. Therefore overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Maximum value node
Full screen
Console