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