Binary Tree Balanced Check Using recursion?

Question

Hello guys, I'm trying to understand how I can see if a binary tree is balanced or not. I tried to print out cout statements in order to try understand it further, but without luck.

The algorithm idea is that it isn't balanced if it returns -1, and is balanced if it returns anything else.

However I don't really grasp how exactly this algorithm is working. But a few things I wonder are;

int checkBalance(node *root)
{
if (root == NULL) return 0;

int left = checkBalance(root->left);
int right = checkBalance(root->right);
 //cout << "Root: " << root->key << " Left: " << left << ", Right: " << right << endl;

if (left == -1 || right == -1) return -1;
if (abs(left-right) > 1) return -1;

if (left > right) return left+1;
return right+1;
}

My points of confusion are with the following lines of code:

1. if (root == NULL) return 0;
   • What happens when it returns 0, and when does it hit 0? Is it just to prevent the recursion to keep going to unknown memory adresses, or does the return number 0 has any significance?

2. if (left > right) return left+1;

   • How is left ever bigger than right? As I'm viewing it, it always returns right+1, cause nothing increments 'left' since the condition never is true?

3. int left = checkBalance(root->left);

   • What does it mean, when you declare an int in this way? Is this the thing which makes left > right?

Thanks for taking your time to read, I have tried to research the problem myself, but I have a hard time understanding how this piece of code works.

Full Code: http://pastebin.com/raw/VaiUNVdJ (case 6 to check, case 1 to add nodes)

Answer 1

This is the basic BBT check. It checks to see whether the subtree is balanced. If not, it returns -1; if so, it returns the depth.

In pseudo-code:

• If the given subtree is null, return 0 (depth)
• Recur on both the left and right subtrees (check balance and depth)
• If either subtree is unbalanced, return -1
• Compare the left & right depths; if they differ by more than 1, return -1
• If we got here, this subtree is balanced. Return its depth. This is the larger of the two subtree depths, plus 1.

To address your specific questions:

1. This algorithm returns the tree depth (-1 if unbalanced). The depth of a null tree is 0.
2. Left is bigger than right any time the left tree is deeper than the right. Do you still have a problem to see this?
3. This is how you declare and initialize a variable. It's the same syntax as in left = 0, except that the assignment's RHS is an expression.

Does that explain enough to get you unstuck?

---

Let's take the node values you gave, using a tree structure with 49 at the root, children 48 and 51, the infix notation could look like:

(48, 49, (50, 51, 52))

In stricter form,

49->left  = 48
49->right = 51
51->left  = 50
51->right = 52
There are no other children

with root = node 49 at the start, we get

int left = checkBalance(root->left);    // returns depth of 1
int right = checkBalance(root->right);  // returns depth of 2

Now, left < right, so the final comparison returns right+1, or 3, which is the correct tree depth.