Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 30 Mar, 2021

Second Minimum Node In A Binary Tree

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

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

Approaches

01 Approach

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.