Binary Tree Traversals

Inorder, Preorder and Postorder

The reason why I am writing this is that it’s a surprisingly simple concept, even though I am not quite sure how people may use these algorithms…

So you have a binary tree, like

Binary Tree

And you want to print (traverse) through the entire tree, and normally it would be like

void print_tree(struct node* node)
{
    // so 3 will be printed immediately
    printf("%d\n", node->val);
    //whenever there is a right node, right node first
    // then 11 999 28 31 17 15
    if (node->right != NULL) print_tree(node->right);
    if (node->left != NULL) print_tree(node->left);
}

Or like

void print_tree(struct node* node)
{
    // call print_tree with a right node immediately if there is one
    if (node->right != NULL) print_tree(node->right);
    // call print_tree with a left node if you dont have a left node
    if (node->left != NULL) print_tree(node->left);
    // begin to print only when there is no more sub-branches
    // then 31 will be printed first then 15 then 17 28 999 11 1 4 9
    printf("%d\n", node->val);
}

Then congratulations! You just wrote the preorder and postorder traversal algorithms. As for the in-order traversal algorithm, it’s a bit weird to write but is quite simple, like

void print_tree(struct node* node)
{
    if (node->right != NULL) print_tree(node->right);
    printf("%d\n", node->val);
    if (node->left != NULL) print_tree(node->left); 
}

As for the result, the inorder way of writing this function will first print all nodes to the right (or left, if you put these function calls in the opposite order) and print the root node and finally nodes to the left (even in the left branch, it will tend to print all nodes to the right first).

The preorder way will immediately print the node it meets and then naturally the root node will be printed first. Then according to the order you place these two function calls, it will first reach either left or right nodes, but it will still be a preorder algorithm either way.

The postorder way will wait until a node finishes searching its both branches (that is, after both print_tree functions have finished execution) before it prints the node, and therefore the root node will be printed last. Then again, according to the order you place these two function calls, it will first reach either left or right nodes, but it will still be a postorder algorithm either way.

If you want to take a look at the entire program, it can be found here (binary tree insertion, search and print using recursion).