00:00

Help Us Improve

We're sorry this tutorial wasn't helpful. Please tell us what we can do better.

Tree Traversals - Inorder, Preorder and Postorder

A tree is a non-linear data structure, it organize and manage data efficiently and allow easier and quicker searching and sorting the data elements.

Tree traversals are methods used to visit and process all the nodes in a tree data structure in a specific order. The three most common traversal techniques for binary trees are Inorder, Preorder, and Postorder. Each traversal method visits nodes in a unique sequence, which is useful for different applications.

Let's see the tree traversal techniques one by one.

1. Inorder Traversal (Left -> Root -> Right)

Inorder Traversal is a method of visiting nodes in a binary tree where we first visit the left subtree, then the root node, and finally the right subtree. This traversal technique is particularly useful for retrieving sorted data from binary search trees, as it processes nodes in ascending order.

In Inorder Traversal, the nodes are visited in the following order:

  1. Traverse the left subtree.
  2. Visit the root node.
  3. Traverse the right subtree.

Example: Tree Inorder Traversal in Java

Node.java 
// Tree Inorder traversal program in Java
class Node {
  int data;
  Node left, right;

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

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

  BinaryTree() {
    root = null;
  }

  // Method to inorder traversal
  void inorderTraversal(Node node) {
    if (node == null)
      return;

    // Traverse left subtree
    inorderTraversal(node.left);
    // Traverse root node
    System.out.print(node.data + " ");
    // Traverse right subtree
    inorderTraversal(node.right);
  }

  public static void main(String[] args) {
    BinaryTree tree = new BinaryTree();
    tree.root = new Node(40);
    tree.root.left = new Node(30);
    tree.root.right = new Node(60);
    tree.root.left.left = new Node(20);
    tree.root.left.right = new Node(35);

    System.out.println("Inorder traversal");
    tree.inorderTraversal(tree.root);
  }
}
Output
Inorder traversal
20 30 35 40 60

2. Preorder Traversal (Root -> Left -> Right)

Preorder Traversal is a method of visiting nodes in a binary tree where we first visit the root node, then left subtree, and finally the right subtree.

In preorder Traversal, the nodes are visited in the following order:

  1. Visit the root node.
  2. Traverse the left subtree.
  3. Traverse the right subtree.

Example: Tree Preorder Traversal in Java

Node.java 
// Tree preorder traversal program in Java
class Node {
  int data;
  Node left, right;

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

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

  BinaryTree() {
    root = null;
  }

  // Method to preorder traversal
  void preorderTraversal(Node node) {
    if (node == null)
      return;

    // Traverse root node
    System.out.print(node.data + " ");
    // Traverse left subtree
    preorderTraversal(node.left);
    // Traverse right subtree
    preorderTraversal(node.right);
  }

  public static void main(String[] args) {
    BinaryTree tree = new BinaryTree();
    tree.root = new Node(40);
    tree.root.left = new Node(30);
    tree.root.right = new Node(60);
    tree.root.left.left = new Node(20);
    tree.root.left.right = new Node(35);

    System.out.println("\nPreorder traversal ");
    tree.preorderTraversal(tree.root);
  }
}
Output
Preorder traversal
40 30 20 35 60

3. Postorder Traversal (Left -> Right -> Root)

Postorder Traversal is a method of visiting nodes in a binary tree where we first visit the left subtree, then the right subtree, and finally the root node.

In Postorder Traversal, the nodes are visited in the following order:

  1. Traverse the left subtree.
  2. Traverse the right subtree.
  3. Visit the root node.

Example: Tree Postorder Traversal in Java

Node.java 
// Tree postorder traversal program in Java
class Node {
  int data;
  Node left, right;

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

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

  BinaryTree() {
    root = null;
  }

  // Method to postorder traversal
  void postorderTraversal(Node node) {
    if (node == null)
      return;

    // Traverse left subtree
    postorderTraversal(node.left);
    // Traverse right subtree
    postorderTraversal(node.right);
    // Traverse root node
    System.out.print(node.data + " ");
  }

  public static void main(String[] args) {
    BinaryTree tree = new BinaryTree();
    tree.root = new Node(40);
    tree.root.left = new Node(30);
    tree.root.right = new Node(60);
    tree.root.left.left = new Node(20);
    tree.root.left.right = new Node(35);

    System.out.println("\nPostorder traversal");
    tree.postorderTraversal(tree.root);
  }
}
Output
Postorder traversal
20 35 30 60 40