find the maximum unbalance of a binary tree

Question

I have the class Bintree that defines a binary tree. I need to implement a method that returns the maximum displacement of the nodes of the tree. So returns a pair of integers; the first of which is the height of t, the second is the maximum imbalance of the subtrees of t. With 'imbalance of a tree' I mean:

imbalance of a tree = absolute value of the difference between the height of the left subtree and the height of the right subtree.

I created the private inner class IntPair to contain the two integers. I know that the method is a recursive method, so I wrote the base case and I think it's correct. Instead I miss the recursive step... What I wrote is wrong. How do I find the maximum value?

public class BinTreeUtil {

    protected static class IntPair {
        int height;
        int maxUnbal;

        IntPair(int h, int u) {
            height = h; 
            maxUnbal = u;
        }
    }

    public static int maxUnbalance(BinTree t) {
        return heightUnbalance(t).maxUnbal;
    }

    private static IntPair heightUnbalance(BinTree t) {
        if(t == null) 
            return new IntPair(-1, 0);
        else {
            int sbil = Math.abs(height(t.left) + height(t.right));
            return new IntPair(height(t), ???);
        }
    }

}

Thanks.

Eran Eran · Accepted Answer · 2014-07-29T19:53:33

You want to maintain both the height and the unbalance during the recursion :

private static IntPair heightUnbalance(BinTree t) {
    if(t == null) 
        return new IntPair(0, 0);
    else {
        IntPair leftResult = heightUnbalance(t.left);
        IntPair rightResult = heightUnbalance(t.right);
        return new IntPair(1+Math.max(leftResult.height,rightResult.height),
                           Math.abs(leftResult.height-rightResult.height));
    }
}

You want to maintain both the height and the unbalance during the recursion :

The height of each node is 1 + the max height of the children.
The imbalance of each node is the absolute value of the difference of heights of the children.
For an empty node, you should return (0,0).

find the maximum unbalance of a binary tree

1 Answers