A tree is a hierachial data structure. An example is a directory tree (excluding any files in the tree): Each directory consists of a name and subdirectories.

Trees are typically drawn as in the diagram below. The circles are the data elements (the names of directories) and the lines below each circle join it to its subtrees (subdirectories).

The data elements in a tree are called *nodes*. The node at the "top"
of a tree is called the *root* (shown in red). The *children*
of a node are the nodes below it and connected to it (like subdirectories in
a directory tree). A *leaf* is a node with no children (sometimes
trees will only store actual data in the leaves).

A node's *parent* is the node above it and
connected to it (every node except the root has a parent).
*Descendants* and *ancestors* are defined in the same way as
family relationships e.g. a parent's parent's parent is an ancestor and a
child's child's child is a descendant. A subtree consists of a node and all
its descendants (which is itself a tree, with the root being the chosen node).

The rest of this page will deal almost entirely with binary trees. A binary
tree is a tree in which every node has at most two children, and the order
of the children is usually important. The children are usually referred to
as the *left child* and the *right child*. Also, if there is
only one child, significance is usually still given to whether it is a left
or a right child.

The *left subtree* of a node is the subtree consisting of the left
child and all its descendants, and likewise for the right subtree.

A binary search tree is a binary tree in which the data elements are of a type with some kind of ordering (e.g. integers or strings). The left subtree of any given node contains only children smaller than that node, and the right subtree contains only children larger than that node (children that are equal can go either way as long as you are consistent).

Binary search trees are usually constructed one element at a time. To add a new element, start at the root and go left if the new element is smaller than the root and right otherwise. Repeat this at each node until you find an unoccupied space and add the new node there.

To search for a given element, follow the same process as with adding a new element until you either find the element you want or find an empty spot, in which case the element isn't there.

You can also convert a binary search tree into a sorted list of the elements by doing a in-order walk of the tree. This is the basis of the binary tree sort.

A "walk" of a tree is basically a way of ordering its elements. There is usually a particular action that has to be performed on each element in the given order.

There are three standard types of walk. All of them are recursive, and all of them involve outputting the root, walking the left subtree and walking the right subtree. The difference is in the ordering. They are as follows:

- Pre-order walk
- Visit the root first, then the left and right subtrees
- In-order walk
- Visit the left subtree, then the root, then the right subtree
- Post-order walk
- Visit the left and right subtrees first, then the root

The in-order walk is particularly useful on a binary search tree, because the elements are visited in sorted order. Walks are generally useful on trees where each node has some logical relation to its subtrees. For example, a tree could have arithmetic operators at nodes, which represent an operation to be applied to the subtrees, and numbers at the leaves. Then an in-order walk would produce normal notation while a post-order walk would produce the Reverse Polish or postfix notation used by old HP calculators.

Last updated Wed May 28 19:34:56.0000000000 2008. Copyright Bruce Merry (bmerry '@' gmail dot. com).