# traversing tree in preorder inorder postorder and level order

Tree as a very common and useful data structure is worth extensive study. Years after I took the Data-structure lesson when I was in school, for the last few days, I regrab the knowledge of how to implement and tranversing a binary tree in servral ways. Besides of the old ways such as preorder/indorder/postorder to traversing a tree, I learnt new knowledge of ways to traversing a tree: level order traversing. Further more, I knew how to print the graph of the tree using graphviz.

Fig.1 a binary tree

The graph above is drawn by graphviz using the output data by our traverse program list below. You can easily figure out the several ways of how to traverse such a binary tree:

As you might have seen, the root-second or the inorder traverse way of such a binary search tree is ordered. In the following section, I will try to (1) constructing a binary tree using basic C structs and pointers. (2) implement different ways of how to traversing a tree.

## Constructing a binary tree

In many books, the Tree and Node structure often share the same defination. However, it is much more clear if you store them seperatly in two different struct. Therefore, you can store additional info in Tree structure inaddtion to Node structure. Currently, the Tree structure only has a member struct _node * which point to the root of the tree. So, I decided to use the following basic data-structure as the fondation brick of my implementation.

Function Tree * new_tree() return an empty tree whose root point to NULL.

## Inserting in to a binary tree

Here we’ll insert values in order so we have a binary search tree. In binary search, lookup and other operations can use the principle of binary search. They allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key.
The insert interface is defined as void insert(Tree *tree, int value), which we insert an int value into the tree. However, a more portable interface is void insert(Tree *tree, void *ptr) which allowing to store a pointer value in the tree. The pointer can point to any other value/struct.
In order to call the insert function recursivily we have a workhorse function insert_internal to do most of the inserting job. Since we have to alter the tree->root pointer when new node is added into the tree, the working horse function’s defination is static void insert_internal(Node **node, int value) in which the address of tree->root is passed as the first argument.
This part of code is below. When inserting a value, if the current position is pointing to NULL we have to allcate a Node structure and store value in it. Else we compare the value against the current node and insert the smaller value into the left part of the tree and the bigger value into the right part of the tree.

## Preorder traversing

Pre-order traversing, also known as root-first traversing(which is more clear), is done by visiting the root first, then the left child, the the right child.

### by using recursive

Recursive make the preorder traversing much simpler and more clear to implement. Much the same as inserting we have two separte functions to do the job. The latter one print_internal is mainly used for recurse purposes.

### by using stack

If we are not using recursive ways, we can also use stack to do the same. This saves lots of function calls which is likely to be much more faster.

It is worth noticing, we have to push right part of the tree first and left part of the tree last, since the stack is LIFO data structure. So the left part is poped out first in the next loop. When the left part is poped out, its value is printed and the right/left part is pushed on the top of the stack. So, always the root first then the left part then the right part.

## inorder traversing

The inorder traversing is done by visiting the left child first, then the root, then the right child last.

## level order traversing

A queue(FIFO) can be used to do the level traversing of a tree. By put the root in queue, then the left child of the root in queue, then the right child of the tree in queue.

This algorithm is worth much thinking to have a full understanding of how it works.

## Graphic output

Any of the above traversing algorithm can be modified to print the edge between the parent and child. Making it much easy to adapt to the graphviz grammer.
One sample of the Fig1 converted to graphviz format is following. Each line representing either a vertex of the tree or the edge of the tree.

It is done by the following code:

Later, issue command dot -Tjpg file.dot -o file.jpg to draw the actual graph as shown in figure1.