getting min and max height of a tree in one traversal of Binary tree in Java?

Question

I have two methods to get min and max height of a binary tree in Java. But I am doing two traversals through the root two times. each is log n in Big(O). Is there a way to compute both min and max in same traversal and return as an array with two indices corresponding to min and max.

Here are my methods

public static int minHeight(Node root){
            if (root==null) return -1;
            return 1+Math.min(minHeight(root.left), minHeight(root.right));
        }

public static int height(Node root){
            if (root==null) return -1;
            return 1+Math.max(height(root.left), height(root.right));

        }

class Node {
        Node left;
        Node right;
        int data;

        public Node(int c){
            this(c, null, null);
        }
        public Node(int c,Node left, Node right) {
            this.data = c;
            this.left=left;
            this.right=right;
        }


    }

Answer 1

Just compute the heights in one pass, and track the min and max as you go. Your confusion lies in the fact that your functions return a single value, but really you need to determine a pair of values. So, you can pass in, say, an object that has a field for both that you can store the results in, and return your results through that instead of through the return value of the function:

class MinMax {
    public int min;
    public int max;
}

void computeMinMaxHeight (Node root, MinMax minmax) {
    // update the fields of minmax accordingly
}

A convenient way to initialize the fields of MinMax might be:

class MinMax {
    public int min = Integer.MAX_VALUE;
    public int max = Integer.MIN_VALUE;
}

Or add some flag that indicates that it is uninitialized, so the values are filled in correctly for the first item.

Edit: You could also return an int[2] array as Changgeng suggests; it just depends on what you find more semantically appropriate. Personally, I'd opt for something like MinMax (Java doesn't really have a standard class for representing value ranges), plus passing the output parameter to the function saves you on object allocations, if that is significant.

Answer 2

Your assertion of Big(O) is incorrect. In your implementation you need to access every node in the tree, so the time complexity would be O(n).

Level order tree traversal could give the answer in one time, but you need two queues to do that correctly.

public int[] findMinMax(Node node) {
    Queue<Node> currentLevel = new LinkedList<Node>();
    Queue<Node> nextLevel = new LinkedList<Node>();

    currentLevel.offer(node);
    int currentHeight = 1;

    int[] result = new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE};
    while (!currentLevel.isEmpty() || !nextLevel.isEmpty()) {

        if (currentLevel.isEmpty()) {
            currentHeight += 1;
            Queue<Node> tmp = nextLevel;
            nextLevel = currentLevel;
            currentLevel = tmp;
        }

        node = currentLevel.poll();
        if (node.left != null) {
            nextLevel.offer(node.left);
        }
        if (node.right != null) {
            nextLevel.offer(node.right);
        }
        if (node.left == null && node.right == null) {
            result[0] = Math.min(result[0], currentHeight);
        }
    }

    result[1] = currentHeight;

    return result;


}

Saying that, it's really not worth it normally. Recursive solution is much easier to write and to understand.

Answer 3

you could always have two properties on each node showing the min and max height of the node.

  this.max = Math.max(this.left.max,this.right.max) + 1 ; 
  this.min = Math.min(this.left.min,this.right.min) + 1;

Answer 4

public class MinMax {

public void printMinMaxNumbers(int[] nums){
    int min = nums[0];
    int max = nums[1];
    for(int n:nums){
        if(n < min){
            min = n;
        } else if(n > max){
            max = n;
        }
    }
    System.out.println("Minimum Number: "+min);
    System.out.println("Maximum Number: "+max);
}

public static void main(String a[]){
    int num[] = {5,34,78,21,79,12,97,23};
    MinMax tmn = new MinMax();
    tmn.printMinMaxNumbers(num);
}

}