# Inorder, preorder and postorder traversal

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.

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

1 2 3 4 5 6 7 8 9 10 | 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**

1 2 3 4 5 6 7 8 9 10 11 12 13 | 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**

1 2 3 4 5 6 7 8 9 10 11 12 13 | 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.