Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Discrete Math
High School Calculators, Computers
High School Discrete Mathematics

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search