Second Minimum Node In A Binary Tree

Easy
0/40
Average time to solve is 20m
profile
Contributed by
5 upvotes
Asked in company
eBay

Problem statement

You are given a Binary Tree with its root node. The Binary Tree holds the following property:

1. Each node has exactly zero or two children.

2. If a node has two children, then the value of the node is the smaller value among its two children or node.->val = min( node.left.val, node.right.val).

Your task is to find the second minimum node value of the tree.

If the second minimum value doesn’t exist, print -1.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

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

alt text

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 : 
For each test case, print the second minimum value of a node in the binary tree.

Print the answer of each test case in a new line.
Constraints : 
1 <= T <= 100
1 <= N <= 3000
1<= data <=10^5 and data!=-1

Time Limit: 1 sec
Sample Input 1 :
2
4 4 5 4 6 5 6 -1 -1 -1 -1 -1 -1 -1 -1
1 -1 -1
Sample Output 1 :
5
-1
Explanation Of Sample Input 1 :
In the first test case, 
Level   -   Nodes
0       -   4
1       -   4, 5
2       -   4, 6, 5, 6
The minimum node value is 4, and the second minimum node value is 5.
In the second test case, 
Level   -   Nodes
0       -   5
The minimum node value is 5 and there is only one node in the tree, So, the second minimum node value doesn’t exist. So, the answer is -1.
Sample Input 2 :
2
1 1 2 1 3 5 2 -1 -1 -1 -1 -1 -1 -1 -1
5 6 5 -1 -1 -1 -1
Sample Output 2 :
2
6
Hint

If we do an Inorder traversal, Can we store all the values and find accordingly?

Approaches (3)
Inorder Traversal

The idea is to perform a recursive Inorder traversal and store all the values in an array. Then sort the array. Iterate over the array, find the first array element which is not equal to the first element of the array(ie. the minimum element of the array), return it as an answer as it is the second minimum element. If the second minimum element doesn’t exist, return -1.   

The steps are as follows:

  • Initialize an array ‘nodeValues’ which stores the value of all the nodes of the binary tree.
  • Define a recursive function ‘InOrderTravesral’ which takes arguments ‘root’, ‘nodeValues’ which denotes the given root node of the binary tree, and the array which stores all the node values.
    • Base Condition is when the root is null, then return from the function as it is a NULL value.
    • Insert the value of the current node in the array ‘nodeValues’.
    • Call the recursive function for the left node of the current node.
    • Call the recursive function for the right node of the current node.
  • When we come out of the recursive function, it means we have stored all the node values.
  • Sort the array ‘nodeValues’.
  • Iterate over the array:
    • If the current element is not equal to the first element of the array ‘nodeValues’, then return it as the final answer as it is the second minimum element.
  • If we come out of the loop, it means the second minimum element doesn’t exist, return -1.
Time Complexity

O( N*log(N) ), where N is the total number of nodes in the given binary tree.

 

As we are visiting every node exactly once which will take O(N) time and then we are sorting the array which contains all the node values which will take O(N*logN) time. Hence, the time complexity is O(N*log(N)).

Space Complexity

O(N), where N is the total number of nodes in the given binary tree.

 

We have a recursion stack that will have a maximum size of N in the worst case(skewed binary tree) which is O(N) and an array to store all the node values which take O(N) space. Hence, the space complexity is O(N).

Code Solution
(100% EXP penalty)
Second Minimum Node In A Binary Tree
Full screen
Console