Lopsided Trees and Recursion

Question

The original problem is:

Define the height of a binary tree to be the number of nodes in the longest path from the root to a leaf. The empty tree is considered to have height 0. A node is k-balanced if its left and right subtrees differ in height by at most k. A tree is k-balanced if all of its nodes are k-balanced. The empty tree is considered to be k-balanced.

For example, the tree below has height 4.

    o
   / \
  o   o
 / \
o   o
   /
  o

This tree is 2-balanced but not 1-balanced, because the left subtree of the root has height 3 and the right subtree of the root has height 1. Your task is to write a method that takes a balance factor k and a number of nodes n and returns the maximum height of a k-balanced tree with n nodes.

One of the answer(right and fast) is:

int fewest_node(int k,int h)
{
    if(h <= 0)
        return 0;
    return 1+fewest_node(k,h-1)+fewest_node(k,h-1-k);
}

int maxHeight2(int k, int n)
{
    for(int h = 1;;h++)
        if(fewest_node(k,h) > n)
            return h - 1;
}

and my solution(terribly slow) is:

int maxHeight(int k, int n)
{
    int i,left,right;
    if(k >= n)
        return n;
    if(n > 2)
    {
        left = maxHeight(k,n-1);
        if(left <= k)
            return left+1;
        else
        {
            i = n - 2;
            left = maxHeight(k,i);
            right = maxHeight(k,n-1-i);
            while((left - right) > k)
            {
                i--;
                left = maxHeight(k,i);
                right = maxHeight(k,n-1-i);
            }
            return left+1;
        }
    }
    else 
        return n;
}

My question:

1. Is my solution really correct? I mean, does it work regardless of its efficiency? Or in other words, is it right logically? (BTW, I think it's right, and I have tested the output when n is less than 30)

2. Why is my solution so slow? As you can see, I'm a newbie to DSA.

Answer 1

I would consider your first question as offtopic. So I will only answer the second question.

For each call to maxHeight you make a lot of recursive calls. Consider what happens if n is large. Say n=100, then can you tell me how many times you call maxHeight? I can't work it out other than "lots". Also consider that you will be calling maxHeight with the same arguments very often, calculating the same results over and over.

Lets look at an example recursive function that bears some resemblance to your code:

int f(int n)
{
    if (n == 0)
        return 1;

    int sum = 0;
    while(n--){ // In your code: while((left - right) > k)
        sum += f(n);
    }
}

While this looks innocent, even for small n you will iterate a really long time. For f(1) you will need one call to f(0). For f(2) you will need one call to f(1) (which calls f(0)) and one to f(0) which totals 3 calls. For f(3) you will need one call to f(2) (which then does 3 more calls), f(1) (which does 1 extra call for you) and f(0) i.e. (3+1) + (1+1) + 1 = 7. Continuing on f(4) will need (7 + 1) + (3 + 1) + (1+1) + 1 = 15. I think you can see where this is heading. For f(n) you will need 2^n-1 calls. So for n=300 you have 2^300 ~= 10^100 calls to f(0). To put that into perspective considering that it's been estimated that there are about 10^80 atoms in the observable universe. I wouldn't want to stick around and wait until that completes. Not even if every atom in the observable universe was a 1 THz computer working optimally in parallel to calculate this.

Your code exhibits the same type of pattern, you make many recursive calls per call to maxHeight so you are probably even worse off.

Comparing to:

int fewest_node(int k,int h)
{
    if(h <= 0)
        return 0;
    return 1+fewest_node(k,h-1)+fewest_node(k,h-1-k);
}

int maxHeight2(int k, int n)
{
    for(int h = 1;;h++)
        if(fewest_node(k,h) > n)
            return h - 1;
}

Calling fewest_node(int j, int h) will result in at most 2^h recursive calls, which is still a lot, but less than your code. But here is the catch, fewest_node() is very simple in structure and the compiler can expand the function in a way similar to loop-unrolling which removes a lot of iteration and overhead. This is a case of K.I.S.Silly.

One way that both of the solutions can be speed up dramatically is by using Dynamic Programming, like this:

#define MAX_N 1000 // Adjust to taste
#define MAX_K 100

int dp_table[MAX_N *MAX_K]={0}; // Not sure if this is legal, otherwise use memset

int fewest_node(int k,int h)
{
    int index = k*MAX_N+h;
    if(!dp_table[index]){
        if(h <= 0)
            return 0;
        dp_table[index] = 1+fewest_node(k,h-1)+fewest_node(k,h-1-k);    
    }
    return dp_table[index];
}

int maxHeight2(int k, int n)
{
    for(int h = 1;;h++)
        if(fewest_node(k,h) > n)
            return h - 1;
}

Simply store each calculated result for fewest_node and start from the bottom up with small h. You can also dynamically allocated a table of the required size when you have received your n and k for the problem. This will drop the worst case time from 2^n to n*k which is eons faster. You can do the same for your code. Just introduce a table of cached results.

Answer 2

// k is the maximum difference in heights between the left and right subtrees
// n is the number of nodes in the tree
int maxHeight(int k, int n) {
    int nodesInLeft, leftHeight, rightHeight;

    // if k is at least n, we can return a height of n
    // because we can simply make a tree of height n and it will be k-balanced
    // if n == 0, the maximum height is 0 (n) for all k >= 0
    // if n == 1, the maximum height is 1 (n) for all k >= 0
    // if n == 2, the maximum height is 2 (n), for all k >= 1
    if ( ( k >= n ) || ( n <= 2 ) {
        return n;
    }

    // try putting as many of the nodes in one tree as possible
    // increase the number of nodes in the other tree until the heights are close enough
    // start with all the nodes but the root node in one tree
    nodesInLeft = n - 1;
    do {
        leftHeight = maxHeight(k, nodesInLeft);
        // nodes in the right subtree equals nodes in the whole tree
        // minus one for the root node minus the number of nodes in the left subtree
        rightHeight = maxHeight(k, n - 1 - nodesInLeft);
        // prepare to try again with one fewer nodes in left and one more in right
        nodesInLeft--;
    } while ( ( leftHeight - rightHeight ) > k );

    // return the height of the taller subtree plus one for the root node
    return leftHeight + 1;
}

If you return in a then or else clause, you don't have to do an else. You can rewrite things so that it just does a return. That happens twice in your original code.

You make a special case for when the right subtree is empty, but you don't have to do so. The loop is capable of processing that case. So rolled it in.

You also do the first calculations for the loop before the loop. This is unnecessary. You can just do the calculations in the loop if you use a do/while rather than a straight while. This also moves the decrement of i/nodesInLeft to the end of the loop, which is a more typical place to put it than the beginning.

I refactored your code and removed all the duplicate code. This is the same algorithm with a shorter implementation. I also gave the local variables more descriptive names and added comments to explain what was happening.

This code will not work when k is less than or equal to zero (except if n is zero or one, when k can be zero). This is problematic because k should be able to be zero. Unfortunately, trees that don't have one fewer than a power of two nodes can't be 0-balanced. The function has no way of communicating that it is impossible to balance.