Last Updated: 30 Mar, 2021
Second Minimum Node In A Binary Tree
Easy
Asked in company
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:
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
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.
The idea is to perform a recursive Inorder traversal and only store two of the smallest values in the binary tree. Initialize two variables to the maximum integer value to store the minimum and second minimum value of the binary tree respectively. If we get a node value that is smaller than the first variable, then we will update both the variables. If we get any node value smaller than the second variable and not equal to the first variable, then we will update the second variable to node value. This step is to save O(N) extra space for the array.
The steps are as follows:
- Initialize two variables, ‘minValue’ and ‘secondMinValue,’ to a maximum integer value(MAX_INT), which stores the minimum node value and the second minimum node value of the binary tree.
- Define a recursive function InOrderTravesral which takes arguments ‘root’, ‘minValue,’ ‘secondMinValue,’ which denotes the given root node of the binary tree, the minimum node value, and the second minimum node value of the binary tree respectively.
- Base Condition is when the root is null, then return from the function as it is a NULL value.
- If minValue is greater than the current node value, then make secondMinValue equal to minValue and minValue equal to current node value.
- Else if the secondMinValue is greater than the current node value and the current node value is not equal to ‘minValue.’ then make secondMinValue equal to current node value.
- Call the recursive function for the left node of the current node.
- Call the recursive function for the right node of the current node.
- If secondMinValue is equal to the maximum integer value, then the second minimum value doesn’t exist. So, return -1.
- Otherwise, return the secondMinValue.
The idea is to use the property of the binary tree given in the problem. Perform the recursive Inorder traversal and recursively call the function only if the value of the current node is equal to the root node value.
The idea behind the step is that we are looking for the second minimum node value, which if exists then, we will get it using this recursive call because the upcoming node value may be equal to or just greater than the current node value.
The steps are as follows:
- Initialize two variables ‘rootNodeValue’ and ‘answer’ to the value of the root node and maximum integer value (INT_MAX), which stores the root node value and the final answer.
- Define a recursive function traversal that takes arguments ‘root’, ‘rootNodeValue’, and ‘answer’, which denotes the given root node of the binary tree, the value of the root node, and the final answer respectively.
- Base Condition is when the root is null, then return from the function as it is a NULL value.
- If the value of the current node is greater than ‘rootNodeValue’ and ‘answer’ is greater than the value of the node value, then update the ‘answer’ to the value of the current node.
- If the value of the node is equal to ‘rootNodeValue’, then recursively call the traversal function for the left sub-tree and right sub-tree.
- If ‘answer’ is equal to the maximum integer value, then the second minimum value doesn’t exist. So, return -1.
Otherwise, return the ‘answer’
.