# Algorithms – Tree traversals

Traversing a tree means that we visit every node in the tree. Every tree is a combination of a node carrying data, and two sub-trees. (left sub-tree and right sub-tree).

Depending on the order we visit all nodes, there are two big categories of traversals:

1. Depth first traversals, achieved through inorder, preorder, or postorder
2. Breadth first traversals, achieved through level order

Letâ€™s assume that the definition of a node is as follows:

## Inorder traversal

Inorder traversal is achieved by:

1. Visiting all the nodes in the left subtree
2. Visiting the root node
3. Visiting all the nodes in the right subtree

Let’s see an example.

• The function is called with the head node = 41.
• According to the algorithm, we go to the left node until is null, then we print the data from that node and go right.
• Therefore, 41 calls 20 which calls 11.
• 11 is done with the left side, so it displays itself {11} and goes to the right (null here, so it returns instead)
• 20 is done with the left side, so it displays itself {11, 20} and goes to the right (29).
• 29 is done with the left side, so it displays itself {11, 20,29} and goes to the right (32).
• 32 is done with the left side, so it displays itself {11, 20,29,32} and goes to the right (null here, so it returns instead).
• 41 is done with the left side, so it displays itself {11,20,29,32,41} and goes to the right (65) which calls 50.
• 50 is done with the left side, so it displays itself {11, 20,29,32,41, 50} and goes to the right (null here, so it returns instead).
• 65 is done with the left side, so it displays itself {11, 20,29,32,41, 50,65} and goes to the right (91) which calls 72.
• 72 is done with the left side, so it displays itself {11, 20,29,32,41, 50,65,72} and goes to the right (null here, so it returns instead).
• 91 is done with the left side, so it displays itself {11, 20,29,32,41, 50,65, 72, 91} and goes to the right (99).
• 99 is done with the left side, so it displays itself {11, 20,29,32,41, 50,65, 72, 91, 99} and goes to the right (null here, so it returns instead).
• The stack unrolls until the last function is removed from the stack.
• In-order traversal displayed the following data: 11, 20,29,32,41, 50,65, 72, 91, 99.

## Preorder traversal

Preorder is achieved by:

1. Visiting the root node
2. Visiting all the nodes in the left subtree
3. Visiting all the nodes in the righ subtree

Let’s see an example.

• The function is called with the head node = 41.
• According to the algorithm, we print the data and then go left side recursively, and then go right side recursively.
• Therefore, 41 displays itself {41} and goes left side. (20)
• 20 displays itself {41,20} and calls left side (11)
• 11 displays itself {41, 20, 11} and has no items to the left nor right, so it goes back to the caller (20) which goes right side now (29)
• 29 displays itself {41,20,11,29} and goes left side (nothing there) so it goes right side (32)
• 32 displays itself {41,20,11,29,32} and have nothing left nor right, so it goes back to the caller (29) -> back to the caller (20) -> back to the caller (41).
• Now that 41 is done with the left side, it goes to the right (65)
• 65 displays itself {41,20,11,29,32, 65} and goes left (50)
• 50 displays itself {41,20,11,29,32, 65,50} and have nothing to the left nor right, so it goes back to the caller (65) which goes right side now (91)
• 91 displays itself {41,20,11,29,32, 65,50,91} and goes left (72)
• 72 displays itself {41,20,11,29,32, 65,50,91,72} and have nothing to the left nor right, so it goes back to the caller (91) which goes right side now (99)
• 99 displays itself {41,20,11,29,32, 65,50,91,72,99} and have nothing left nor right, so it goes back to the caller (91) -> back to the caller (65) -> back to the caller (41) -> pop out of the stack.
• Pre-order traversal displays the following data: 41,20,11,29,32, 65,50,91,72,99.

## Postorder traversal

Postorder is achieved by:

1. Visiting all the nodes in the left subtree
2. Visiting all the nodes in the right subtree
3. Visiting the root node

Let’s see an example.

• The function is called with the head node = 41.
• According to the algorithm, we go left side recursively, then right side recursively, then we print the data.
• Therefore, 41 goes left side (20).
• 20 goes left side (11).
• 11 have nothing on the left, nothing on the right, so it prints itself {11} and goes back to the caller (20).
• 20 goes right side (29).
• 29 have nothing on the left, so it goes on the right (32).
• 32 have nothing on the left, nothing on the right, so it prints itself {11, 32} and goes back to the caller (29).
• 29 displays itself {11, 32, 29} and goes back to the caller (20).
• 20 displays itself {11, 32, 29, 20} and goes back to the caller (41).
• 41 goes right side (65).
• 65 goes left side (50).
• 50 have nothing on the left or right, so it prints itself {11, 32, 29, 20, 50} and goes back to the caller (65).
• 65 does right side (91).
• 91 goes left side (72).
• 72 have nothing on the left or right, so it prints itself {11, 32, 29, 20, 50, 72} and goes back to the caller (91).
• 91 goes right side (99).
• 99 have nothing on the left or right, so it prints itself {11, 32, 29, 20, 50, 72, 99} and goes back to the caller (91).
• 91 displays itself {11, 32, 29, 20, 50, 72, 99, 91} and goes back to the caller (65).
• 65 displays itself {11, 32, 29, 20, 50, 72, 99, 91, 65} and goes back to the caller (41).
• 41 displays itself {11, 32, 29, 20, 50, 72, 99, 91, 65, 41}  and pops out of the stack.
• Post-order traversal displayed the following data: 11, 32, 29, 20, 50, 72, 99, 91, 65, 41.

## Level order traversal

Level order traversal is achieved by visiting all nodes at a particular level, before visiting the nodes of a deeper level.

Let’s see an example.

In order to implement such traversal, we will need to use a queue.

As we visit a node, we can add all the children in the queue, to later visit them. As long as the queue is not empty, we can take out a node from the front of the queue, visit it, and then enqueue its children.

• With our structure, we will start by adding 41 in the queue.
• The queue is not empty, so we pop the item from the queue, and add its children instead.
• Therefore, after the first run, we will have the first level traversed (the root node), and we have its left and right children in the queue. {20, 65}.
• For the 2nd iteration, we pop the first item in the queue, which is 20. Now, the queue contains only the value 65.
• By adding the left and right children (next depth) to the queue, the queue will be {65, 11, 29}.
• We can see that we cannot visit the next level until all the items from level 2 are visited yet.

Level-order traversal displays the following data: 41, 20, 65, 11, 29, 50, 91, 52, 72, 99.