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$

closed as unclear what you're asking by David Richerby, Evil, Juho, Rick Decker, Tom van der Zanden Feb 22 '17 at 11:12

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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.