Isn't this a balanced binary tree?

1
votes

Isn't the tree in the image given below a balanced binary tree? One of my friends was arguing that this can't be balanced because the node A is at depth 2 from the root E and G and L are at depth 4 from E and hence E has to unbalanced by a factor of -2. My belief is that the node is only unbalanced if:

Absolute(Heigh of left subtree - Height of right subtree) > 1

The height of the left subtree of E is 3 because of D and not 2. What would be the best way to convince my friend??

Balanced Tree

1
algorithmtree
You're arguing about two definitions of the word "balanced." You can't argue one is better than the other... you just have to pick one. – Paul Hankin

1 Answers

1
votes

According to Wikipedia, it's balanced if it's the minimum possible height. In this case, you could move both leaves 'G' and 'L' to 'A', and the tree height would be 4. There is a way to make the height smaller, so the tree is not balanced. Any tree with height ceil(log2(n)) would be balanced.