Tree Traversals - Inorder, Preorder and Postorder

   Last Updated: 06 October, 2024       🕓  5 Mins Read

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

// 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

// 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

// 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