Particular Algorithm For Binary Tree - Complexity must be O(n)

Question

I have to write a program that can verify if the binary tree satisfies this property:

for each node of the tree, the height of its subtrees (right and left) must differ for max 1.

Not good:

Good:

The algorithm I built has a O((n^2)log(n)) complexity.

Thanks for Helping!

bool check(node* root){
    if(!root->right && !root->left){
        return;
    }

    int h;
    int n_node;
    int hRight, hLeft;

    h = height(root);
    hRight = height_right(root);
    hLeft = height_left(root);

    n_node = pow(2, heihgt+1)-1;

    if((hRight > n_node/2 && hLeft <= n_node/4) ||  (hLeft > n_node/2 && hRight <= n_node/4)
       return true;
}

I know is not good-looking but it is an attempt. Notice that this algorithm is O(nlog(n)) since it works only for the firts node (root). So i have to put it inside another block to scroll nodes.

http://www.geeksforgeeks.org/how-to-determine-if-a-binary-tree-is-balanced/ — Daniel Nugent, Jun 20 '16 at 23:15
@DanielNugent thank you for your answer. I was very near to the solution but the algorithm that is suggested in the page is not O(n) since it calculates the height of the tree twice — David, Jun 21 '16 at 00:10
@David look at the "optimized" solution below the initial solution on that page, it's O(n) — Daniel Nugent, Jun 21 '16 at 00:16
It's actually even more simple than that, take a look at the code here: https://leetcode.com/discuss/99284/clean-and-simple-c-solution — Daniel Nugent, Jun 21 '16 at 00:19
Possible duplicate of [to find out if a binary tree is balanced or not efficiently](http://stackoverflow.com/questions/17515571/to-find-out-if-a-binary-tree-is-balanced-or-not-efficiently) — Paul Hankin, Jun 21 '16 at 03:17

molbdnilo · Accepted Answer · 2016-06-21T18:45:51.790

It's unclear why you're counting nodes when the definition of a balanced tree is right in front of you – in terms of height, not number of nodes.

The tricky part is that if you compute the depth and check for balance separately, you're going to end up with too great a complexity (O(n^2), I think).

So you need a helper function that computes both as it traverses the tree.
This is a pretty straightforward solution:

// Returns whether 'root' is a balanced tree.
// Also stores the tree's height in *height.
bool balanced_height(node* root, int* height)
{
   // The trivial base case – an empty tree is balanced and has height 0.
   if (root == nullptr)
   {
      *height = 0;
      return true;
   }

   // Information gathering using recursion:
   // Find out whether the subtrees are balanced, and get their heights.
   int leftheight = 0;
   int rightheight = 0;
   bool leftbalance = balanced_height(root->left, &leftheight);
   bool rightbalance = balanced_height(root->right, &rightheight);

   // Now that we know the heights of the subtrees,  we can store the height of this tree.
   *height = max(leftheight, rightheight) + 1;

   // Finally, a translation into C++ of the definition:
   // A tree is balanced if and only if
   //   - the subtrees are balanced, and
   //   - the heights of the subtrees differ by at most one.
   return leftbalance && rightbalance && abs(leftheight - rightheight) <= 1;
}

bool balanced(node* root)
{
     int height = 0;
     return balanced_height(root, &height);
}

It can be made slightly faster (but with the same complexity) in the unbalanced case by not traversing the second subtree if the first is unbalanced, since we're not going to use the height for anything in that case.
That optimisation is left as an exercise.

Thank you for your answer. I made a step-by-step "debug" and i tried to understand the algorithm. It's amazing and at the same time very complicated. I'm now trying to optimize it. It have to put a control in the right place to stop the algorithm. — David, Jun 21 '16 at 15:07
@David It's not that complicated; it basically has four parts (which I'd hidden too well...) all of which are rather simple. I added some comments that might clarify things. — molbdnilo, Jun 21 '16 at 18:48

Particular Algorithm For Binary Tree - Complexity must be O(n)

1 Answers1