MinimumAndMaximumInTheBinaryTree.java

// Minimum and Maximum in the Binary Tree
// Send Feedback
// 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

// Following is the structure used to represent the Binary Tree Node

class BinaryTreeNode<T> {
    T data;
    BinaryTreeNode<T> left;
    BinaryTreeNode<T> right;

    public BinaryTreeNode(T data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

// Representation of the Pair Class

class Pair<T, U> {
    T minimum;
    U maximum;

    public Pair(T minimum, U maximum) {
        this.minimum = minimum;
        this.maximum = maximum;
    }

}

class Solution {
    public static int maximum(BinaryTreeNode<Integer> root) {
        if (root == null) {
            return Integer.MIN_VALUE;
        }

        int leftMax = maximum(root.left);
        int rightMax = maximum(root.right);
        return Math.max(root.data, Math.max(leftMax, rightMax));
    }

    public static int minimum(BinaryTreeNode<Integer> root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }

        int leftMin = minimum(root.left);
        int rightMin = minimum(root.right);
        return Math.min(root.data, Math.min(leftMin, rightMin));
    }

    public static Pair<Integer, Integer> getMinAndMax(BinaryTreeNode<Integer> root) {
        // Your code goes here
        int min = minimum(root);
        int max = maximum(root);

        return new Pair<>(min, max);
    }

}