1
$\begingroup$

Can someone please explain to me how the Wikipedia example on the left for a balanced binary tree is correct?

One common balanced tree structure is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1

For node ABCDE, isn't the height of left subtree 2 and the height of the right subtree 0, making the difference of height 2?

EDIT As David rightly pointed out:

That page defined "balanced" immediately above the example you're asking about, and it defines balanced in a different way to you.

I thought that the example was using the definition that comes immediately after the example, which I have quoted above. Apologies for the confusion.

$\endgroup$
  • $\begingroup$ I don't understand your question. That page defined "balanced" immediately above the example you're asking about, and it defines balanced in a different way to you. The tree you're asking about is balanced in the sense the page talks about. $\endgroup$ – David Richerby Feb 11 '17 at 10:42
3
$\begingroup$

That Wikipedia article is using a different definition of "balanced":

A balanced binary tree has the minimum possible height.

Therefore, since a perfect binary tree of height $d$ has $2^{d}-1$ nodes, if a tree has $n$ nodes, the minimum possible height for that tree is $\left \lceil \log_2n \right \rceil$, and the tree you mention does indeed satisfy that condition.

Observe that the usual definition of "balanced tree" is in an asymptotic setting, i.e. depth is $\mathcal{O}(\log n)$.

$\endgroup$

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