Binary Search Trees

Date: 02/06/2003 at 18:47:59
From: Ben Ullian
Subject: C++ and AP Computer Science Exam

Consider the following characters to be entered into an empty binary 
search tree.

'A' 'B' 'C' 'D' 'E' 'F' 'G'

Which of the following sequences represent(s) an order of insertion
that will result in a binary search tree where each node in the tree
has the same number of nodes in its left and right subtrees?

I. 'D' 'B' 'F' 'A' 'E' 'C' 'G'
II. 'D' 'E' 'F' 'G' 'C' 'B' 'A'
III. 'D' 'F' 'G' 'E' 'B' 'A' 'C'
(A) I only
(B) II only
(C) III only
(D) I and III only
(E) I, II, and III

No matter which order you use, you always end up with a binary tree 
that has even subtrees on both right and left sides. Since there are 
7 elements, the tree should fully fill the first three levels.

Without any significance to the letters (they are said to be "just 
characters"), the order doesn't seem to have any meaning.

In terms of binary *search* trees, the process used is to divide a 
list into halves, choose the half with the thing you want, then split 
that into halves and select recursively until you end up with the 
thing you are looking for. This makes a type of tree (splitting) 
formation, but I do not think that this applies here because you don't 
know the character you are "searching" for.

Date: 02/07/2003 at 03:21:58
From: Doctor Jacques
Subject: Re: C++ and AP Computer Science Exam

Hi Ben,

There are two different things to consider in binary trees:

(1) How we search a binary tree for a given element.

(2) How the tree is built incrementally by inserting elements.

The question here relates to problem (2). Note that there may be many 
different search trees for the same data, depending on the order in 
which elements are inserted.

The easy way to build a tree is best illustrated by considering the 
second sequence:

  'D' 'E' 'F' 'G' 'C' 'B' 'A'

We start by inserting D - there is no choice available in this, we 
just store D as the root:

   D

Now we insert E. We do that by searching the tree for E; if we don't 
find it, we insert it at the next empty place where it would have to 
be. As E > D, we have to move right from D, and we find an empty 
place, so we store E there:

     D
      \
       E

To insert F, we start at D, move right, find E, move right (since
F > E), and find an empty place, so we store F there:

     D
      \
       E
        \
         F

The procedure for G is similar:

     D
      \
       E
        \
         F
          \
           G

To insert C, we start at D, and, since C < D, we look left and find 
an empty slot:

     D
    / \
   C   E
        \
         F
          \
           G

To insert B, we follow the path D -> C -> (left) :

     D
    / \
   C   E
  /     \
 B       F
          \
           G

And finally, we insert A by following the path D -> C -> B -> (left)

       D
      / \
     C   E
    /     \
   B       F
  /         \
 A           G

You will notice that, in this case, some nodes do NOT have the same 
number of children in their left and right subtrees; for example node 
C has 2 children on the left subtree and none on the right subtree - 
we say that the tree is not "balanced."

I'll let you use the same procedure for the other two insertion 
sequences.

If the tree were balanced, there would be just 3 levels: we could find 
an element by doing at most three comparisons. In the example above, 
we may, in some cases, need 4 comparisons. If the tree is to be used 
intensively, it is best to have it balanced.

The procedure described above is the "easy" way to insert elements. 
There are other, more complicated procedures that can be used to build 
the tree in such a way that it is almost balanced; this improves 
performance on searching. One of these methods involves re-arranging 
some nodes at each step in order to keep the tree balanced.

You will find easily that (with this easy procedure) the worst case 
happens when the elements to be inserted are already in ascending or 
descending order - in that case, you end up with a linear structure, 
in which each node has only one child; it's no longer a "binary" 
tree.

On the other hand, if the elements are inserted in random order, there 
is a good chance that the resulting tree will be decently balanced, 
but you can never be sure of that.

Please feel free to write back if you want to discuss this further.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/