**Binary
Search Trees**

•

Linked lists are great and very volatile but as we have seen, accessing information can be quite slow. The reason for that is, that we have to go through every value in the list until we reach our desired item. The complexity for such a task is O(n), which is quite long especially for programs that load a lot of information in to memory. Programmers tried to figure out a way that makes inserting and searching for information as volatile as pointers but quicker. The solution to that problem was binary trees. Access time for binary trees is O(log2n) which is significantly faster.

Below is a great excerpt describing trees.

*Binary trees consist of
nodes and arcs. Unlike natural trees they are depicted upside down with the root
at the top and the leaves (terminal nodes) at the bottom. The root is a node
that has no parent and only has child nodes. Leaves on the other hand, have no
children, or rather, their children are null. A tree can be defined recursively
as the following:*

*1. An empty structure
is a tree*

*2. If t1....tk
are disjointed trees then the structure whose root has as its children the roots
t1....tk is also a tree.*

*3. Only structures
generated by rules 1 and 2 are trees.*

*A path is a
sequence of arcs, from the root to a node which is unique for every node.*

*The number of arcs is
the length of the path.*

*The height of a
tree is the maximum level of a node in the tree. *

**Tree traversal **is
the process of visiting each node in the tree exactly one time.

**Drozdek, Adam (2005)
Data Structures and Algorithms in JAVA, Second Edition, USA Thomson Learning
Inc.**

The way you go through a
tree is very simple. When a value we are searching for is bigger or equal to (in
value) the node we are currently at, we move to the right of the tree and visit
the right node (its right child), or else, we move to the left of the tree and
visit the left node.* *Starting from the root of the tree, we traverse the
tree as described above.* *

Three commonly used traversals are:

a) **Pre order traversal**,
where the sequence followed is: Visit a node, Traverse its left sub-tree then
traverse its right sub-tree.

b) **In order traversal**,
where first you traverse the left sub-tree of a node, then you visit the node
and then its right sub-tree.

c) **Post order traversal**,
where you traverse the left sub-tree of a node, then the right sub tree and then
the node itself.

**Applet
Instructions**

In the following applet, you can add
numbers to the tree and search for values you have added. This should provide
you with a good understanding of the basis of binary search trees. **The applet
limits the numbers you can add from** **1-99**.
After you have added some values (at least one), you can click on the traversal
buttons and the traversed order will appear in the textbox below.

Home | Arrays | Arrays2 | Queues1 | Queues2 | Stacks | Arguments | Pointers |

Binary Search Tree