I have seen two definitions of balanced binary trees, which look different to me.

  1. A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.

  2. A binary tree is balanced if for any two leaves the difference of the depth is at most 1.

Does every tree that satisfies def. 1 also satisfy def. 2? What about the other way round?

  • 2
    $\begingroup$ Have you tried proving either direction? What are your findings? $\endgroup$ – Raphael Sep 12 '12 at 22:31

Definition 1. is also known as weight-balancedness¹ and definition 2. as height-balancedness.

Height-balancedness does not imply weight-balancedness; examples are both AVL- and Red-Black-Trees. See here and here for proofs, respectively.

Weight-balancedness does imply height-balancedness, though. This can be proven by showing the following stronger fact by induction (over height): a weight-balanced tree is complete on all levels but the deepest². The essential argument in the inductive step is that the subtrees can't have a height difference of more than one because -- both having the claimed property by induction hypothesis -- they would then not be weight-balanced.

  1. The article gives a different, more general definition.
  2. In other words, such a tree of height $k$ without the leaves at level $k$ is a perfect tree of height $k-1$.
  • $\begingroup$ I just realised that the stronger fact can be used to wastly simplify the proofs I link to. $\endgroup$ – Raphael Sep 12 '12 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.