Proving tree is balanced from subtrees's balancedness

Question

I'm solving the following problem from "Cracking the Coding Interview": Implement a function to check if a binary tree is balanced. A balanced tree is a tree such that the heights of the two subtrees of any node never differ by more than one.

The book's sample solution (copied below) assumes the tree emanating from a node is balanced if (a) the node's left and right subtrees are balanced; and (b) the node itself is balanced. I'm trying to understand why this is the case? How does the fulfillment of the above two conditions prove that the entire tree emanating from the node is balanced?

Thanks

public static boolean isBalanced(TreeNode root)
{
    if (checkHeight(root)==-1)
        return false;
    return true;
}


public static int checkHeight(TreeNode root)
{
    //base case
    if (root == null)
        return 0;

    //is left subtree balanced
    int leftHeight = checkHeight(root.leftChild);

    if (leftHeight == -1)
        return -1;

    //is right subtree balanced
    int rightHeight = checkHeight(root.rightChild);

    if (rightHeight == -1)
        return -1;

    //is current node balanced
    int heightDiff = leftHeight - rightHeight;

    if (Math.abs(heightDiff) > 1)
        return -1;

    return (Math.max(leftHeight, rightHeight) + 1);
}

Answer 1

This is an application of recursion – the routine calculates heights of the left and the right subtree of the node being checked, and recursively validates the subtrees at the same time. It returns -1 if it finds any node unbalanced or the subtree height if it is okay. The comparision of subtrees' heights decides whether the current node is balanced or not.

BTW, replace root with currnode in the whole checkHeight() function to make it clear how the routine applies recursively to every node in a tree, not just its root.

Answer 2

A balanced binary tree is one in which the total depth of the left and right sub-trees differ by no more than one[1]. Here, the solution presented is recursive, and first checks whether the children are themselves balanced or not, and then checks whether the parent is balanced. It does this by checking the depth of the child's left and right sub-trees, and if the depth between them differs by atmost 1, it returns max(left_depth,right_depth)+1. If not, it returns -1. The algorithm then continues this for the entire tree. If the depth is -1 at any point (indicating that a child isn't balanced), the overall depth of the sub-tree is returned as -1. Finally, simply check if the total depth of the tree is -1: if so, the tree isn't balanced, otherwise, it is.

Here's the algorithm in the form of an induction:

• Base case

  Leaf node- trivially balanced, with 0 children. It returns 1, since the depth would include both the number of children (0) as well as the node itself.

• Inductive case

  An intermediate node, which will be balanced if the children are balanced, and the depth of the left child differs from that of the right by atmost 1. If balanced, it returns the max(left_depth,right_depth) + 1, representing the total depth of the tree, including the node itself. If not balanced, simply return -1.

• Finally

  Root node, checked like the inductive case, but if balanced, then the entire tree is balanced, with total depth being max(left_depth,right_depth) + 1, where left_depth and right_depth represent the depths of the left/right sub-trees with respect to the root node.

A previously asked SO question that covers several very interesting aspects of coding up a BST may be found here.

Answer 3

Since you asked for it, here some more on induction:

https://en.wikipedia.org/wiki/Well-founded_relation

Forget everything you know about induction, here is the real thing. If we have some relation R, R is said to be well-founded if and only if there is no infinitely descending chain x1, x2, x3, ... with x1 R x2, x2 R x3 and so on. ("descending" because people are thinking of < on numbers )

For example, < is well-founded on the natural numbers, but not on real numbers.

With well-founded relations, you have that

(for all x : (for all y : x R y -> P(y)) -> P(x)) <-> for all x : P(x)

In other words, it is enough to show that all minimal elements wrt. R have some property, and then show that if all smaller elements than some x fulfill P, so does x.

Special case is the induction you probably know:

(P(0) & for all n: P(n) -> P(n+1)) -> for all n: P(n) (the well-founded relation here is the successor function)

For finite trees, the subtree relation is (obviously) well-founded, so we can do (actually let's use the transitive closure, makes the proof shorter. It is still well-founded):

Base case: (leafs, these are mininal wrt subtree relation) leafs with 0 children are balanced, trivially

Induction: Assuming all subtrees (and their subtrees and so on) are balanced, and the root node is balanced, all nodes are balanced, no node is left that could be unbalanced (see what I did here?)

We could have done this without using the transitive closure if we also note that to be balanced implies that the subtrees are balanced. Then we can just say that having the direct subtrees balanced implies that all their subtrees are balanced as well, and we are back at my proof.