Understanding Binary Search Tree construction

The shape that a binary search tree takes depends on two things:

1. The order in which the elements are inserted, and
2. What balance operations, if any, the tree does during insertion.

If you have a pure binary search tree with no rebalancing logic whatsoever, then the order in which the elements are inserted will have a strong impact on the shape of the tree. For example, take the values 1, 2, 3, 4, 5, 6, 7. If you insert them in the order 4, 2, 6, 1, 3, 5, 7, you will get this tree:

        4
      /   \
     2     6
    / \   / \
   1   3 5   7

The reason for this is that we go through the following series of trees:

     4

     4
   /
  2

     4
   /   \
  2     6 

     4
   /   \
  2     6
 /
1

     4
   /   \
  2     6
 / \
1   3

     4
   /   \
  2     6
 / \   /
1   3 5

     4
   /   \
  2     6
 / \   / \ 
1   3 5   7

On the other hand, if you insert the values in the order 1, 2, 3, 4, 5, 6, 7, you get this tree:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7

Interestingly, inserting elements into a BST in sorted order is one of the worst things you can do for the tree, since it makes the tree a linear structure. You are better off picking a random permutation of the elements to insert, or (if they're all known in advance) sorting them and using the following recursive algorithm on the sorted sequence:

• If there are no elements, you are done.
• Otherwise:
  • Insert the median into the BST.
  • Recursively insert the first half of the elements into the BST.
  • Recursively insert the second half of the elements into the BST.

Hope this helps!