C++ Binary Tree Balanced Check Using recursion? -


hello guys, i'm trying understand how can see if binary tree balanced or not. tried print out cout statements in order try understand further, without luck.

the algorithm idea isn't balanced if returns -1, , balanced if returns else.

however don't grasp how algorithm working. few things 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 following lines of code:

  1. if (root == null) return 0;
    • what happens when returns 0, , when hit 0? prevent recursion keep going unknown memory adresses, or return number 0 has significance?
  2. if (left > right) return left+1;

    • how left ever bigger right? i'm viewing it, returns right+1, cause nothing increments 'left' since condition never true?
  3. int left = checkbalance(root->left);

    • what mean, when declare int in way? thing makes left > right?

thanks taking time read, have tried research problem myself, have hard time understanding how piece of code works.

full code: http://pastebin.com/raw/vaiunvdj (case 6 check, case 1 add nodes)

this basic bbt check. checks see whether subtree balanced. if not, returns -1; if so, returns depth.

in pseudo-code:

  • if given subtree null, return 0 (depth)
  • recur on both left , right subtrees (check balance , depth)
  • if either subtree unbalanced, return -1
  • compare left & right depths; if differ more 1, return -1
  • if got here, subtree balanced. return depth. larger of 2 subtree depths, plus 1.

to address specific questions:

  1. this algorithm returns tree depth (-1 if unbalanced). depth of null tree 0.
  2. left bigger right time left tree deeper right. still have problem see this?
  3. this how declare , initialize variable. it's same syntax in left = 0, except assignment's rhs expression.

does explain enough unstuck?


let's take node values gave, using tree structure 49 @ root, children 48 , 51, infix notation like:

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

in stricter form,

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

with root = node 49 @ start, get

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

now, left < right, final comparison returns right+1, or 3, correct tree depth.


Comments