If you have been working with linear data structures like stacks and queues, you know that it is a pretty easy job to traverse them. They are linear, which tells us that they are also traversed linearly. One simply goes through one element at a time, in a linear fashion.

Note: If you’re serious about becoming a great programmer, I encourage you to check out this Comprehensive Java Course. It thoroughly explains crucial concepts every Java developer should know, without wasting too much time on the “too easy” introductory stuff (since you’re reading about tree traversal, I assume you’re familiar with the basics.. 😉 )

With trees however, it is not so intuitive. Just think about it; What would it even mean to traverse a tree “linearly”? Would you traverse through it one level at a time? Or would you traverse the tree one sub-tree at a time?

If you’re given the task to traverse a tree, you have to go at it another way.
Luckily, the work has already been done for us, and there are primarily 4 ways to traverse a tree ;

  • Inorder traversal
  • Preorder traversal
  • Postorder traversal
  • Levelorder traversal (which we’ll look at another time).

Note that you should be familiar with both the tree data structure and recursion before proceeding.

Before we explain the above mentioned ways to traverse a tree, let’s get familiar with some crucial terms used when describing the tree data structure.

  • A tree consists of a set of objects (nodes).
  • Every tree, unless empty, has a root node.
  • Every node, apart from the root node, is connected to another node by a directed edge.
  • If node B is connected by an edge from node A, then B is A’s child, and A is B’s parent.
  • The path to any given node is unique.

Visualization of a tree data structure

This picture clearly showcase the important parts of the tree data structure. And for the relationships between the nodes:

  • B and F are children of D.
  • A and C are children of B.
  • E and G are children of F.

Now, let’s start with the actual tree traversal!

Inorder traversal

Inorder traversal is done in the following order: left –> root –> right.

Explaining this by an example, using the tree visualized above;

  • Enter D. Move to D’s left sub-tree.
  • Enter B. Move to B’s left sub-tree.
  • Enter A. There is no left sub-tree. Process root, which is A. There is no right sub-tree. Move back up to B.
  • Enter B. B’s left sub-tree is processed. Process B. Move to B’s right.
  • Enter C. There is no left sub-tree. Process root, which is now C. There is no right sub-tree. Move back up to B.
  • Enter B. B has already been processed. Move to D.
  • Enter D. D’s left sub-tree is processed. Process D. Move to D’s right sub-tree.
  • Enter F. Move to F’s left sub-tree.
  • Enter E. No sub-trees. Process E. Move back up to F.
  • Enter F. Already processed left sub-tree. Process F. Move to F’s sub-tree.
  • Enter G. Process G.

Phew, alot of steps! The final result of the inorder traversal is: A B C D E F G

The java code to perform this traversal recursively can be seen below

public void printInOrder(Node node) {
        if (node == null)
            return;
        // Traversing down the left side
        printInOrder(node.left);
        // Printing value
        System.out.print(node.element.toString() + " ");
        // Traversing down the right side
        printInOrder(node.right);
    }

Preorder traversal

Preorder traversal are performed in the following order: root –> left –> right.

The steps to traverse the tree in this article is as follows:

  • Enter D. D is root, process D.
  • Enter B. B is root, process B.
  • Enter A. A is root, process A. No sub-trees, move back up to B.
  • Enter B. Move to right sub-tree.
  • Enter C. C is root, process C.
  • Done with right sub-tree, move back up to D.
  • Enter F. Process F. Move to left sub-tree.
  • Enter E. Process E. Move back up.
  • Enter F. Move to right sub-tree.
  • Enter G. G is root, process G.

The resulting order is: D B A C F E G

public void printPreOrder(Node node) {
        if (node == null)
            return;

        // Printing value
        System.out.print(node.element.toString() + " ");

        // Traversing left sub-tree
        printPreOrder(node.left);

        /* Traversing right sub-tree
        printPreOrder(node.right);
    }

Postorder traversal

Traversing a tree in postorder is done like this: left –> right –> root.

  • Enter A. Move to left sub-tree.
  • Enter B. Move to left sub-tree.
  • Enter A. No left sub-tree. Process A. Move to B.
  • Enter B. Move to right sub-tree.
  • Enter C. No sub-trees. Process C. Move to B.
  • Enter B, process B. Move back up to A.
  • Enter A. Move to A’s right sub-tree.
  • Enter F. Move to F’s left sub-tree.
  • Enter E. Process E. Move back up to F.
  • Enter F. Move to right sub-tree.
  • Enter G. Process G.
  • Move back up to starting position, process F and D.

The result of the postorder traversal is: A C B E G F D

    public void printPostOrder(Node node) {
        if (node == null)
            return;

        // Traversing left sub tree
        printPostOrder(node.left);

        // Traversing right subtree
        printPostOrder(node.right);

        // Printing value
        System.out.print(node.element.toString() + " ");
    }

As you have probably noticed, all three of the traversal orders can be solved in just a few lines of code using recursion.
This is the very reason why I didn’t include the level order traversal – which can’t be solved easily using recursion.