[Solved]: Balancing a Binary Search Tree

Problem Detail: 

I was reading about binary search trees on it's Wikipedia article. I was a little confused by this image. Why is it that the right branch to the head node does not have a sub-tree? I understand why it can be valid like this but surely the "8" could branch to "13" instead, then "10" and "14" could become the descendants of "13". It seems like this would be far more balanced. So I researched around for more information about binary search tree balancing and I'm still unsure. Why is the diagram in the Wikipedia article was favored? Is my suggestion wrong?

Depth-first in-order traversal still works as I presume the same for all other traversal methods.

Asked By : user103853

Answered By : john_leo

Yes, the right subtree could be $13(10,14)$.
But notice that the article you've linked discusses the most naive version of building a Binary Search Tree, in which numbers are simply inserted into the tree one-after-another without balancing. So in your example first the $10$ was inserted, then the $14$, then $13$. Of course there are plenty of other algorithms that balance the tree (they are also linked in the Wiki-article).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32939

3.2K people like this

 Download Related Notes/Documents