Tree Traversal (Inorder, Preorder, Postorder)

What is Tree Traversal?

In the tree data structure, traversal means visiting nodes in some specific manner. There are two types of traversals. Generally, this kind of traversal is based on the binary tree. A binary tree means each node can have a maximum of 2 nodes.

A binary tree is a well-known data structure. There’s also a Binary Search tree (BST). This type of traversal is used for various purposes. The level order traversal, it’s used for calculating the depth between two nodes. There’s another kind of tree called “AVL”, where calculating the height of a node is necessary. We can represent a Binary tree in the array, but for memory optimization, we’ll use structure and pointer for referencing the next node.

Types of Tree Traversal

As we discussed binary trees, now we discuss the individual types of traversals. Depending on the types, there are two types of traversal. Previously we’ve mentioned the necessity of level order or Breadth-First Traversal. Now Depth-First Traversal like post order is used for deletion of a node (we’ll discuss it later on), preorder is used for copying a Binary tree, and “inorder” will traverse the tree in a nondecreasing manner.

• Breadth-First Traversal
• Depth-First Traversal
• Pre-order traversal
• Post-order traversal
• In-order traversal

Breadth-First Traversal

It’s also known as the level-order traversal. Let’s consider the following tree for demonstrating the level-order traversal.

So, we will start from the root node “1”. It will be marked as level 1. Then the algorithm will go to all the children of the current node. We’ll visit node 2 and 3 now. They will be marked as level 2.

After that, as we have 2 nodes in level 2, we’ll visit their children too. So, we will visit 5,6,8,7 and mark them as level 3. Here’s a thing no mention,

Level of node = parent node’s level + 1

Level 1: 1

Level 2: 2 3

Level 3: 5 6 8 7

A similar algorithm is used for the BFS (Breadth-First-Search).

Here’s the Pseudocode for level order traversal:

level_order(node)
Q → Queue()
Q.push(node)
while !Q.empty():
    current_node = Q.pop()
    print current_node.value
# Checking if the current node have any child or not
if current_node.left is not NULL:
    Q.push(current_node.left)
if current_node.right is not NULL:
    Q.push(current_node.right)

Inorder Traversal Binary Tree

Let’s have the same example as before. In this type of traversal, we first visit the left subtree, then the root, and after that, the right subtree. For ease of remembering, we can say in order goes like left-root-right.

For the entire tree, let’s say the root is 1. Now the algorithm will follow:

• Visit the left subtree of node 1.
• The current node is 2 (as it’s the left subtree of 1)

• Visit the left subtree of 2. The current node will be 5 this time.
• Moving to 5, it has no children, so node 5 will be marked as visited. It will return to the parent node; which is 2.
• As the left subtree of 2 is visited, now 2 will be visited as well.
• The algorithm will move the current node to the right subtree of node 2, which is node 6. After visiting node 6. It will move to its parent node 2.
• As node 2 is visited, now we will visit the parent of 2; which is node 1.
• After that, we’ll visit the right subtree.

So the final traversal will look like this:

InOrder: 5 → 2 → 6 → 1 → 8 → 3 → 7

Here’s the Pseudocode for In-order traversal:

InOrder(node):
  if node is not null:
    InOrder(node.left)
  print node.value
    InOrder(node.right)

This is the recursive algorithm for the inorder traversal. For the Binary Search Tree (BST), Inorder traversal gives the sorted array of values.

Post-Order Traversal

In this traversal, we will traverse the leftmost subtree first, then the rightmost subtree after the root. All the traversals will be in Post-Order. Let’s demonstrate an example:

Here for root = 1,

• We’ll go to the left subtree first. So the root will become 2.
• Then 2 has left subtree, so we will go to node 5. Now the root is 5.
• It has no left subtree, also it has no right subtree. So, now we will mark node 5 as visited and we’ll go to its parent node.

• Now the root is 2 and its left subtree is completely visited. We’ll now move to its right subtree. So the root becomes 6.
• As node 6 has no left and right subtree, we will mark node 6 visited and move to its parent node 2.
• Now, both the left and right subtree are being visited for node 2. It’ll be marked as visited too.
• We’ll move to the parent of node 2, which is node 1.
• The left subtree is visited for root 1. Now similarly, we’ll visit the right subtree.

The circle marked is the right subtree. Now we will visit the right subtree as we visited the left subtree. After that, we will visit the node. So the final traversal will be:

PostOrder: 5 → 6 → 2 → 8 → 7 → 3 → 1

Here’s the Pseudocode for Post-order traversal:

PostOrder(node):
    if node is not null:
       PostOrder(node.left)
       PostOrder(node.right)
       print node.value

Preorder Traversal

For the preorder traversal, the algorithm will visit the root node first, after that, it will move to the left and right subtree, respectively. For ease of understanding, we can think of preorder traversal visits like root → left-right.

So, let’s select node 1 as the root.

• As per the algorithm, the root will be discovered first, then the left, and then the right subtree.
• So, we’ll visit root 1. Then we will move to its left subtree. The root becomes 2.
• We’ll visit node 2 and move to its left subtree. So, the root becomes 3.
• We visit node 3, then we move to its parent node. Now node 2 and its left subtree are visited. Time for visiting the right subtree.
• We’ll move to the right subtree, the root becomes 4. We’ll visit 4. As 4 has no child node, we’ll move to its parent.
• Now root is 2 and it is visited along with its left and right subtree. So, we’ll move to its parent node. Now root becomes 1.
• Similarly, we’ll visit the right subtree.

PreOrder: 1 → 2 → 3 → 4 → 5 → 6 → 7

Here’s the Pseudocode for Pre-order traversal:

PreOrder(node):
   if node is not null:
     print node.value
         PreOrder(node.left)
         PreOrder(node.right)

Implementation in Python

class Node:
    def __init__(self, item):
    self.left = None
self.right = None
self.val = item
# creating a tree data structure
def inorder(root):
#checking if the root is null or not
if root:
    inorder(root.left)
# recursively calling left subtree
print(str(root.val) + " ", end = '')
inorder(root.right)
# recursively calling right subtree
def postorder(root):
    if root:
    postorder(root.left)
postorder(root.right)
print(str(root.val) + " ", end = '')
def preorder(root):
    if root:
    print(str(root.val) + " ", end = '')
preorder(root.left)
preorder(root.right)
def levelOrder(root):
    queue = list()
queue.append(root)
while len(queue) >
0:
    current = queue[0]
queue = queue[1: ]
print(str(current.val) + " ", end = "")
if current.left:
    queue.append(current.left)
if current.right:
   queue.append(current.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("\nLevelOrder traversal:\t", end = " ")
levelOrder(root)
print("\nInorder traversal:\t", end = " ")
inorder(root)
print("\nPreorder traversal:\t", end = " ")
preorder(root)
print("\nPostorder traversal:\t", end = " ")
postorder(root)

Output:

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

Implementation in C

#include <stdio.h>
#include <stdlib.h>
struct node {
   int value;
   struct node* left;
   struct node* right;
};
// Inorder traversal
void InOrder(struct node* root) {
   if (root == NULL) return;
   InOrder(root->left);
   printf("%d ", root->value);
   InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Inorder traversal:\t");
  InOrder(root);
  printf("\PreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

OutPut:

Inorder traversal: 4 2 5 1 6 3 7
Preorder traversal: 1 2 4 5 3 6 7
Postorder traversal: 4 5 2 6 7 3 1

Implementation of C++ (Using std::queue for level order)

#include <stdio.h>
#include <stdlib.h>
#include<queue>
typedef struct node {
  int value;
  struct node* left;
  struct node* right;
}node;
// Inorder traversal
void InOrder(struct node* root) {
  if (root == NULL) return;
  InOrder(root->left);
  printf("%d ", root->value);
  InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
void LevelOrder(struct node* root){
   std::queue<struct node*> Q;
   Q.push(root);
   while(!Q.empty()){
   struct node* current = Q.front();
   Q.pop();
   printf("%d ",current->value);
 if(current->left)
   Q.push(current->left);
 if(current->right)
   Q.push(current->right);
  }
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = new node();
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Level Order traversal:\t");
  LevelOrder(root);
  printf("\nInorder traversal:\t");
  InOrder(root);
  printf("\nPreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

FAQs