28
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Have you tried proving either direction? What are your findings? $\endgroup$
    – Raphael ♦
    Sep 12, 2012 at 22:31

1 Answer 1

Reset to default
18
$\begingroup$

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$.
Improve this answer
$\endgroup$
4
  • $\begingroup$ I just realised that the stronger fact can be used to wastly simplify the proofs I link to. $\endgroup$
    – Raphael ♦
    Sep 12, 2012 at 22:47
  • $\begingroup$ Perhaps it is a good idea to incorporate this realization in your answer. $\endgroup$
    – Discrete lizard ♦
    May 22, 2019 at 13:50
  • $\begingroup$ @Discretelizard You mean, the other answers? $\endgroup$
    – Raphael ♦
    Jun 26, 2019 at 9:51
  • $\begingroup$ Oh, I didn't realize those links were answers on Computer Science or that they were your answers. Well, in any case, all I wanted to say is that it might be a good idea to write the simplified proofs down. Your linked answers then seem to be the appropriate place. $\endgroup$
    – Discrete lizard ♦
    Jun 26, 2019 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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