-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBinary Trees2-Minimum and Maximum in the Binary Tree
49 lines (44 loc) · 1.61 KB
/
Binary Trees2-Minimum and Maximum in the Binary Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
For a given a Binary Tree of type integer, find and return the minimum and the maximum data values.
Return the output as an object of Pair class, which is already created.
Note:
All the node data will be unique and hence there will always exist a minimum and maximum node data.
Input Format:
The first and the only line of input will contain the node data, all separated by a single space. Since -1 is used as an indication whether the left or right node data exist for root, it will not be a part of the node data.
Output Format:
The only line of output prints two integers denoting the minimum and the maximum data values respectively. A single line will separate them both.
Constraints:
2 <= N <= 10^5
Where N is the total number of nodes in the binary tree.
Time Limit: 1 sec
Sample Input 1:
8 3 10 1 6 -1 14 -1 -1 4 7 13 -1 -1 -1 -1 -1 -1 -1
Sample Output 1:
1 14
Sample Input 2:
10 20 60 -1 -1 3 50 -1 -1 -1 -1
Sample Output 2:
3 60
******************************************Solution**********************************************
private static Pair<Integer,Integer> maxMin=new Pair<Integer,Integer>(Integer.MAX_VALUE, Integer.MIN_VALUE);
public static Pair<Integer, Integer> getMinAndMax(BinaryTreeNode<Integer> root) {
getMinAndMaxHelper(root);
return maxMin;
}
private static void getMinAndMaxHelper(BinaryTreeNode<Integer> root)
{
if(root==null)
return;
int rootData=root.data;
int maxVal=maxMin.maximum;
if(rootData>maxVal)
{
maxMin.maximum=root.data;
}
int minVal= maxMin.minimum;
if(rootData<minVal)
{
maxMin.minimum=root.data;
}
getMinAndMax(root.left);
getMinAndMax(root.right);
}