# Two definitions of balanced binary trees

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?

• Have you tried proving either direction? What are your findings? – 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$.
• I just realised that the stronger fact can be used to wastly simplify the proofs I link to. – Raphael Sep 12 '12 at 22:47
• Perhaps it is a good idea to incorporate this realization in your answer. – Discrete lizard May 22 '19 at 13:50
• @Discretelizard You mean, the other answers? – Raphael Jun 26 '19 at 9:51
• 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. – Discrete lizard Jun 26 '19 at 21:02