Binary Search Tree of Strings (before balancing)

Question

I'm reading up on Binary Search Trees and I have a question to answer similar to Ordered Binary Tree of Strings

Are the trees I've drawn below correct for before and after balancing? The data being entered are the strings, in order of, Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus

Before balancing:

      Mercury
     /       \
   Earth     Venus
     \        /
    Mars   Saturn
    /         \
Jupiter      Uranus

After balancing:

          Mercury
         /       \
   Jupiter        Uranus
   /     \        /     \
Earth   Mars   Saturn  Venus

Is it also correct that the depth of the first tree is 3 and the depth of the second tree is 2, and that the maximum size is 7 (based on n = 2^(d+1)-1 where d = depth?

Bernhard Barker Bernhard Barker · Accepted Answer · 2013-12-12T21:54:32

Yes, the balancing looks correct as the binary search tree ordering is correct (for any given node, all nodes in the left subtree are smaller and all nodes in the right subtree are larger) and it's perfectly balanced.

Although I'm not sure there's a generic "balance the tree" algorithm (at least not one I've heard of). There are however self-balancing BST's like red-black trees and AVL trees.

Yes, the depths are correct, as per Wikipedia:

The depth (or height) of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a depth of zero.

Yes, the maximum size calculation is also correct. You can think of this as follows:
The maximum size is 1 + 2 + 4 + 8 + ... + 2^depth (each term corresponds to the maximum number of nodes per level).
That is 1111111...111 (depth 1's) in binary.
And, of course, the above plus one is 100000...000 (depth 0's), which is 2^{depth + 1}.
Subtracting the one again, we get 2^{(depth + 1)} - 1.

Binary Search Tree of Strings (before balancing)

1 Answers