Tree Traversal - inorder, preorder & postorder

In this tutorial, you will learn about various tree traversal methods. Likewise, you will discover working instances of various tree traversal methods in C, C++, Java, and Python.

In this article, you will learn-

1 What is tree traversal?
2 Inorder traversal
3 Preorder traversal
4 Postorder traversal
5 Python, Java, and C/C++ Examples

What is tree traversal?

A tree is a widely used data structure in the world of programming. This structure, similar to its name, has branches and subdivisions, where every element in the tree is known as a node.

For a tree to be “traversed” implies that each node inside the tree has been visited.

Where most data structures can be traversed in a couple of ways by virtue of being linear, trees have a hierarchical structure and consequently they can be traversed multiplely. Before we comprehend what these sorts are, we should be acquainted with a couple of terms.

• root: The first node of the tree (by and large depicted as the top-most node).

• parent: Each node that has a branch leading out from it, is known as the parent of the subsequent node(s).

• children: The node(s) that extend out from the parent are called

children; the left and the right child contingent upon the position of the node.

Traversing a tree implies visiting each node in the tree. You may, for example, need to add all the values in the tree or find the largest one. For every one of these activities, you should visit every node of the tree.

Linear data structures like arrays, stacks, queues, and linked list have just a single method to read the data. In any case, a hierarchical data structure like a tree can be traversed in different ways.

Let’s think about how we can read the elements of the tree in the picture that appeared above.

Beginning from top, Left to right

1 -> 12 -> 5 -> 6 -> 9

Beginning from bottom, Left to right

5 -> 6 -> 12 -> 9 -> 1

Albeit this process is somewhat simple, it doesn’t respect the hierarchy of the tree, just the depth of the nodes.

Instead, we use traversal techniques that consider the essential structure of a tree for example

struct node {
    int data;
    struct node* left;
    struct node* right;
}

The struct node highlighted by left and right may have other left and right kids so we should consider them sub-trees rather than sub-nodes.

As indicated by this structure, each tree is a combination of

A node conveying information

Two subtrees

Remember that our goal is to visit each node, so we need to visit all the nodes in the subtree, visit the root node and visit all the nodes in the right subtree too.

depending upon the order in which we do this, there can be three sorts of traversal.

Inorder traversal

First, visit all the nodes in the left subtree
Then the root node
Visit all the nodes in the right subtree

inorder(root->left)
display(root->data)
inorder(root->right)

Preorder traversal

Visit root node
Visit all the nodes in the left subtree
Visit all the nodes in the right subtre

display(root->data)
preorder(root->left)
preorder(root->right)

Postorder traversal

Visit all the nodes in the left subtree
Visit all the nodes in the right subtree
Visit the root node

postorder(root->left)
postorder(root->right)
display(root->data)

Let’s visualize in-order traversal. We start from the root node.

We traverse the left subtree first. We additionally need to make sure to visit the root node and the right subtree when this tree is finished.

Let’s put all this in a stack so that we remember.

Presently we traverse to the subtree pointed on the TOP of the stack.

Once more, we observe a similar rule of inorder

Left subtree -> root -> right subtree

After traversing the left subtree, we are left with

Since the node “5” doesn’t have any subtrees, we print it straightforwardly. After that we print its parent “12” and afterward the right child “6”.

Putting everything on a stack was useful because now that the left-subtree of the root node has been traversed, we can print it and go to the right subtree.

In the wake of experiencing all the elements, we get the inorder traversal as

5 -> 12 -> 6 -> 1 -> 9

We don’t need to make the stack ourselves since recursion maintains the correct order for us.

Python, Java, and C/C++ Examples

Python

# Tree traversal in Python


class Node:
    def __init__(self, item):
        self.left = None
        self.right = None
        self.val = item


def inorder(root):

    if root:
        # Traverse left
        inorder(root.left)
        # Traverse root
        print(str(root.val) + "->", end='')
        # Traverse right
        inorder(root.right)


def postorder(root):

    if root:
        # Traverse left
        postorder(root.left)
        # Traverse right
        postorder(root.right)
        # Traverse root
        print(str(root.val) + "->", end='')


def preorder(root):

    if root:
        # Traverse root
        print(str(root.val) + "->", end='')
        # Traverse left
        preorder(root.left)
        # Traverse right
        preorder(root.right)


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Inorder traversal ")
inorder(root)

print("\nPreorder traversal ")
preorder(root)

print("\nPostorder traversal ")
postorder(root)

Java

// Tree traversal in Java

class Node {
  int item;
  Node left, right;

  public Node(int key) {
  item = key;
  left = right = null;
  }
}

class BinaryTree {
  // Root of Binary Tree
  Node root;

  BinaryTree() {
  root = null;
  }

  void postorder(Node node) {
  if (node == null)
    return;

  // Traverse left
  postorder(node.left);
  // Traverse right
  postorder(node.right);
  // Traverse root
  System.out.print(node.item + "->");
  }

  void inorder(Node node) {
  if (node == null)
    return;

  // Traverse left
  inorder(node.left);
  // Traverse root
  System.out.print(node.item + "->");
  // Traverse right
  inorder(node.right);
  }

  void preorder(Node node) {
  if (node == null)
    return;

  // Traverse root
  System.out.print(node.item + "->");
  // Traverse left
  preorder(node.left);
  // Traverse right
  preorder(node.right);
  }

  public static void main(String[] args) {
  BinaryTree tree = new BinaryTree();
  tree.root = new Node(1);
  tree.root.left = new Node(12);
  tree.root.right = new Node(9);
  tree.root.left.left = new Node(5);
  tree.root.left.right = new Node(6);

  System.out.println("Inorder traversal");
  tree.inorder(tree.root);

  System.out.println("\nPreorder traversal ");
  tree.preorder(tree.root);

  System.out.println("\nPostorder traversal");
  tree.postorder(tree.root);
  }
}

// Tree traversal in C

#include <stdio.h>
#include <stdlib.h>

struct node {
  int item;
  struct node* left;
  struct node* right;
};

// Inorder traversal
void inorderTraversal(struct node* root) {
  if (root == NULL) return;
  inorderTraversal(root->left);
  printf("%d ->", root->item);
  inorderTraversal(root->right);
}

// preorderTraversal traversal
void preorderTraversal(struct node* root) {
  if (root == NULL) return;
  printf("%d ->", root->item);
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

// postorderTraversal traversal
void postorderTraversal(struct node* root) {
  if (root == NULL) return;
  postorderTraversal(root->left);
  postorderTraversal(root->right);
  printf("%d ->", root->item);
}

// Create a new Node
struct node* createNode(value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->item = value;
  newNode->left = NULL;
  newNode->right = NULL;

  return newNode;
}

// Insert on the left of the node
struct node* insertLeft(struct node* root, int value) {
  root->left = createNode(value);
  return root->left;
}

// Insert on the right of the node
struct node* insertRight(struct node* root, int value) {
  root->right = createNode(value);
  return root->right;
}

int main() {
  struct node* root = createNode(1);
  insertLeft(root, 12);
  insertRight(root, 9);

  insertLeft(root->left, 5);
  insertRight(root->left, 6);

  printf("Inorder traversal \n");
  inorderTraversal(root);

  printf("\nPreorder traversal \n");
  preorderTraversal(root);

  printf("\nPostorder traversal \n");
  postorderTraversal(root);
}

C++

// Tree traversal in C++

#include <iostream>
using namespace std;

struct Node {
  int data;
  struct Node *left, *right;
  Node(int data) {
    this->data = data;
    left = right = NULL;
  }
};

// Preorder traversal
void preorderTraversal(struct Node* node) {
  if (node == NULL)
    return;

  cout << node->data << "->";
  preorderTraversal(node->left);
  preorderTraversal(node->right);
}

// Postorder traversal
void postorderTraversal(struct Node* node) {
  if (node == NULL)
    return;

  postorderTraversal(node->left);
  postorderTraversal(node->right);
  cout << node->data << "->";
}

// Inorder traversal
void inorderTraversal(struct Node* node) {
  if (node == NULL)
    return;

  inorderTraversal(node->left);
  cout << node->data << "->";
  inorderTraversal(node->right);
}

int main() {
  struct Node* root = new Node(1);
  root->left = new Node(12);
  root->right = new Node(9);
  root->left->left = new Node(5);
  root->left->right = new Node(6);

  cout << "Inorder traversal ";
  inorderTraversal(root);

  cout << "\nPreorder traversal ";
  preorderTraversal(root);

  cout << "\nPostorder traversal ";
  postorderTraversal(root);

Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.