What is the difference between preorder and postorder and inorder?

In this tutorial, you will learn what a binary search tree is, what parts make up a tree, and some of the common terms we use when describing parts of a tree.

We will also see how to traverse a tree using some of the common algorithms – all illustrated with clear examples.

What Is a Binary Search Tree?

A binary search tree is a binary tree made up of nodes. Each node has a key signifying its value.

The value of the nodes on the left subtree are smaller than the value of the root node. And the value of the nodes on the right subtree are larger than the value of the root node.

The root node is the parent node of both subtrees.

The diagram below shows the main parts of a binary tree:

Diagram of a binary search tree

Let's us look at the relationship between the nodes.

• A is the root node.
• The left subtree begins at B while the right subtree begins at C.
• Node A has two child nodes – B and C.
• Node C is the parent node to F and G. F and G are siblings.
• Node F and G are know as leaf nodes because they do not have children.
• Node B is the parent node to D and E.
• Node D is the parent node to H and I.
• D and E are siblings as well as H and I.
• Node E is a leaf node.

So here are some important terms that we just used to describe the tree above:

Root: The topmost node in the tree.

Parent: A node with a child or children.

Child: A node extended from another node (parent node).

Leaf: A node without a child.

What Is a Binary Search Tree Used For?

Binary search trees help us speed up our binary search as we are able to find items faster.

We can use the binary search tree for the addition and deletion of items in a tree.

We can also represent data in a ranked order using a binary tree. And in some cases, it can be used as a chart to represent a collection of information.

Next, we'll look at some techniques used in traversing a binary tree.

What is Tree Traversal?

Traversing a tree means visiting and outputting the value of each node in a particular order. In this tutorial, we will use the Inorder, Preorder, and Post order tree traversal methods.

The major importance of tree traversal is that there are multiple ways of carrying out traversal operations unlike linear data structures like arrays, bitmaps, matrices where traversal is done in a linear order.

Each of these methods of traversing a tree have a particular order they follow:

• For Inorder, you traverse from the left subtree to the root then to the right subtree.
• For Preorder, you traverse from the root to the left subtree then to the right subtree.
• For Post order, you traverse from the left subtree to the right subtree then to the root.

Here is another way of representing the information above:

Inorder => Left, Root, Right.

Preorder => Root, Left, Right.

Post order => Left, Right, Root.

How to Traverse a Tree Using Inorder Traversal

We are going to create a tree similar to the one in the last section, but this time the node keys will be numbers instead of letters.

Remember that the values of the nodes on the left subtree are always smaller than the value of the root node. Also, the values of the nodes on the right subtree are larger than the value of the root node.

Here is the diagram we will be working with:

Recall that the order for inorder traversal is Left, Root, Right.

This is the result we get after using inorder traversal:

D, B, E, A, F, C, G

If that seems a bit complex for you to understand, then follow the order of the colors in the picture below

Inorder traversal

How to Traverse a Tree Using Preorder Traversal

The order here is Root, Left, Right.

Using the same diagram above, we have:

A, B, D, E, C, F, G

Here is the same diagram with different colors used as a guide:

Preorder traversal

How to Traverse a Tree Using Postorder Traversal

The order for post order traversal is Left, Right, Root.

Here is the output:

D, E, B, F, G, C, A

If you can't figure out how we arrived at that result, then use the colors in the picture below as a guide:

Postorder traversal

Conclusion

In this tutorial, we learned the basics of what a binary search tree is, what the various parts of a binary tree are, and the common terms associated with a tree. We also saw some of the algorithms we can use to traverse a tree.

Thank you for reading!

Binary Tree Traversals

Traversal is a common operation performed on data structures. It is the process in which each and every element present in a data structure is "visited" (or accessed) at least once. This may be done to display all of the elements or to perform an operation on all of the elements.

For example, to traverse a singly-linked list, we start with the first (front) node in the list and proceed forward through the list by following the next pointer stored in each node until we reach the end of the list (signified by a next pointer with the special value nullptr). A doubly-linked list can also be traversed in reverse order, starting at the last (back) node in the list and proceeding backwards down the list by following the prev pointer stored in each node, stopping when we reach the beginning of the list (signified by a prev pointer with the special value nullptr). Arrays can likewise easily be traversed either forward or backward, simply by starting with either the first or last element and then incrementing or decrementing a subscript or pointer to the array element.

On the other hand, binary trees can be traversed in multiple ways. These notes describe four different traversals: preorder, inorder, postorder, and level order.

The "Tick Trick"

This is a handy trick for figuring out by hand the order in which a binary tree's nodes will be "visited" for the preorder, inorder, and postorder traversals.

1. Draw an arrow as a path around the nodes of the binary tree diagram, closely following its outline. The direction of the arrow depends on whether you are traversing the tree left-to-right or right-to-left.
2. Draw a line or tick mark on one of the sides or the bottom of each node in the tree. Where you draw the mark depends on which traversal you are attempting to perform, as shown in the diagram below:

The point at which the path you've drawn around the binary tree intersects the tick mark is the point at which that node will be "visited" during the traversal.

Preorder Traversal

In a preorder traversal of a binary tree, we "visit" a node and then traverse both of its subtrees. Usually, we traverse the node's left subtree first and then traverse the node's right subtree.

Here's an example of a left-to-right preorder traversal of a binary tree:

Printing the value of each node as we "visit" it, we get the following output:

    A B X E M S W T P N C H

Alternatively, we can perform a preorder traversal from right-to-left instead of left-to-right. This is done by traversing the node's right subtree before we traverse its left subtree.

Printing the value of each node as we "visit" it, we get the following output:

    A W C H T N P B S X M E

Note that the left-to-right preorder traversal and the right-to-left preorder traversal are not mirror images of each other.

Recursive Preorder Traversal Pseudocode

Given the recursive nature of binary trees (each subtree is itself a binary tree), it's very easy to write preorder traversal as a recursive algorithm. The base case for the recursion occurs when the tree (or subtree) we are attempting to traverse is empty (i.e., the node pointer is nullptr).

procedure preorder(p : pointer to a tree node)
    if p != nullptr
        Visit the node pointed to by p
        preorder(p->left)
        preorder(p->right)
    end if
end procedure

On the initial call to the preorder() procedure, we pass it the root of the binary tree. To convert the pseudocode above to a right-to-left traversal, just swap left and right so that the right subtree is traversed before the left subtree.

Iterative Preorder Traversal Pseudocode

Preorder traversal can also be performed using a non-recursive or iterative algorithm. In order to backtrack up the tree from a node to its parent, we use a stack.

procedure iterative_preorder()
    // root : pointer to the root node of the tree (nullptr if tree is empty)
    // p    : pointer to a tree node
    // s    : a stack of pointers to tree nodes

    // Start at the root of the tree.
    p ← root

    // While p is not nullptr or the stack is not empty... 
    while p != nullptr or s is not empty

        // Go all the way to the left.
        while p != nullptr
            Visit the node pointed to by p

            // Place a pointer to the node on the stack before
            // traversing the node's left subtree.
            s.push(p)
            p ← p->left
        end while

        // p must be nullptr at this point, so backtrack one level.
        p ← s.top()
        s.pop()

        // We have visited the node and its left subtree, so
        // now we traverse the node's right subtree.
        p ← p->right

    end while
end procedure

Inorder Traversal

In an inorder traversal of a binary tree, we traverse one subtree of a node, then "visit" the node, and then traverse its other subtree. Usually, we traverse the node's left subtree first and then traverse the node's right subtree.

Here's an example of a left-to-right inorder traversal of a binary tree:

Printing the value of each node as we "visit" it, we get the following output:

    E X M B S A P T N W H C

Alternatively, we can perform an inorder traversal from right-to-left instead of left-to-right. This is done by traversing the node's right subtree before we traverse its left subtree.

Printing the value of each node as we "visit" it, we get the following output:

    C H W N T P A S B M X E

Note that the left-to-right inorder traversal and the right-to-left inorder traversal are mirror images of each other.

Recursive Inorder Traversal Pseudocode

Pseudocode for a recursive inorder traversal is a minor variation of the pseudocode for the recursive preorder traversal:

procedure inorder(p : pointer to a tree node)
    if p != nullptr
        inorder(p->left)
        Visit the node pointed to by p
        inorder(p->right)
    end if
end procedure

Iterative Inorder Traversal Pseudocode

Inorder traversal can also be performed using a non-recursive or iterative algorithm, in a fashion very similar to the iterative preorder traversal.

procedure iterative_inorder()
    // root : pointer to the root node of the tree (nullptr if tree is empty)
    // p    : pointer to a tree node
    // s    : a stack of pointers to tree nodes

    // Start at the root of the tree.
    p ← root

    // While p is not nullptr or the stack is not empty... 
    while p != nullptr or s is not empty

        // Go all the way to the left.
        while p != nullptr

            // Place a pointer to the node on the stack before
            // traversing the node's left subtree.
            s.push(p)
            p ← p->left
        end while

        // p must be nullptr at this point, so backtrack one level.
        p ← s.top()
        s.pop()

        // We have visited this node's left subtree, so now we
        // visit the node.
        Visit the node pointed to by p

        // We have visited the node and its left subtree, so
        // now we traverse the node's right subtree.
        p ← p->right

    end while
end procedure

Postorder Traversal

In a postorder traversal of a binary tree, we traverse both subtrees of a node, then "visit" the node. Usually we traverse the node's left subtree first and then traverse the node's right subtree.

Here's an example of a left-to-right postorder traversal of a binary tree:

Printing the value of each node as we "visit" it, we get the following output:

    E M X S B P N T H C W A

Alternatively, we can perform a postorder traversal from right-to-left instead of left-to-right. Once again, this is done by traversing the node's right subtree before we traverse its left subtree.

Printing the value of each node as we "visit" it, we get the following output:

    H C N P T W S M E X B A

Note that the left-to-right postorder traversal and the right-to-left postorder traversal are not mirror images of each other. However, we can now see that the left-to-right postorder traversal is a mirror image of the right-to-left preorder traversal, while the right-to-left postorder traversal is a mirror image of the left-to-right preorder traversal.

Recursive Postorder Traversal Pseudocode

Once again, pseudocode for a recursive inorder traversal is just a minor variation of the pseudocode for the recursive preorder and inorder traversals:

procedure postorder(p : pointer to a tree node)
    if p != nullptr
        postorder(p >left)
        postorder(p->right)
        Visit the node pointed to by p
    end if
end procedure

Iterative Postorder Traversal Pseudocode

Postorder traversal can also be performed using a non-recursive or iterative algorithm. This is a trickier algorithm to write than the iterative preorder or inorder traversals, since we will need to backtrack from a node to its parent twice. Some sources solve this problem (poorly, in my opinion) by using two different stacks. Donald Knuth's The Art of Computer Programming has a more efficient version of the algorithm that maintains an extra pointer to the node that was last visited and uses it to distinguish between backtracking to a node after traversing its left subtree versus backtracking to a node after traversing its right subtree.

procedure iterative_postorder()
    // root         : pointer to the root node of the tree (nullptr if tree is empty)
    // p            : pointer to a tree node
    // last_visited : pointer to the last tree node visited
    // s            : a stack of pointers to tree nodes

    // Start at the root of the tree.
    last_visited ← nullptr
    p ← root

    while p != nullptr and last_visited != root
   
        // Go all the way to the left.
        while p != nullptr and p != last_visited
 
            // Place a pointer to the node on the stack before
            // traversing the node's left subtree.
            s.push(p)
            p ← p->left
        end while

        // p must be nullptr at this point, so backtrack one
        // level.
        p ← s.top()
        s.pop()

        // If this node has no right child or we've already traversed
        // its right subtree...
        if p->right == nullptr or p->right == last_visited

            Visit the node pointed to by p

            // Mark this node as the last visited.
            last_visited ← p
        else
			// Otherwise, traverse the node's right subtree.
            s.push(p)
            p ← p->right
        end if
    end while
end procedure

Level Order Traversal

In a level order traversal of a binary tree, we traverse all of the tree nodes on level 0, then all of the nodes on level 1, etc. The "tick trick" does not work for this traversal, but there's no real need for it, since the order the nodes will be traversed is easy to determine by hand.

Here's an example of a left-to-right level order traversal of a binary tree:

Printing the value of each node as we "visit" it, we get the following output:

    A B W X S T C E M P N H

Alternatively, we can perform a level order traversal from right-to-left instead of left-to-right.

Printing the value of each node as we "visit" it, we get the following output:

    A W B C T S X H N P M E

Iterative Level Order Traversal Pseudocode

Level order traversal can be performed using a non-recursive or iterative algorithm. As a given level is traversed, a queue is used to store pointers to the nodes on the next level.

procedure iterative_level_order()
    // root : pointer to the root node of the tree (nullptr if tree is empty)
    // p    : pointer to a tree node
    // q    : a queue of pointers to tree nodes
    
    // If tree is empty, return.
    if root == nullptr
        return
    end if
    
    q.push(root)
    
    while q is not empty
    
        // Remove front item in the queue and visit it.
        p ← q.front()
        q.pop()
        Visit the node pointed to by p
        
        // Insert left child of p into queue.
        if p->left != nullptr
            q.push(p->left)
        end if

        // Insert right child of p into queue.
        if p->right != nullptr
            q.push(p->right)
        end if
    end while
end procedure

Recursive Level Order Traversal Pseudocode

Level order traversal can also be written as a recursive algorithm; here's one example of a solution:

procedure level_order()
    // root : pointer to the root node of the tree (nullptr if tree is empty)
    // h    : computed height of the tree (i.e., number of levels
    // i    : loop counter
    
    h ← height(root);

    i ← 1
    while i <= h
        print_level(root, i)
        i ← i + 1
     end while
end procedure

procedure print_level(p : pointer to a tree node, level : level number)
    if p == nullptr
        return

    if level == 1
        Visit the node pointed to by p
    else if level > 1
        print_level(p->left, level-1)
        print_level(p->right, level-1)
    end if
end procedure

procedure height(p : pointer to a tree node)
    // l_height : computed height of node's left subtree
    // r_height : computed height of node's right subtree
    
    if p == nullptr
        return 0
    end if

    l_height ← height(p->left)
    r_height ← height(p->right)

    if l_height > r_height
        return l_height + 1
    else
        return r_height + 1
    end if
end procedure