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

Last updated:

To traverse a tree is to visit each of its nodes exactly once. Unlike an array, a binary tree has no single natural order, so we have to choose one. The three classic depth-first orders are inorder, preorder and postorder. All three go down the left subtree before the right subtree; they differ only in when the current node itself is processed.

All the examples on this page use the same tree:

      40
     /  \
   30    60
  /  \
20    35

Each traversal visits every node once, so each takes O(n) time; the recursion uses O(h) stack space, where h is the height of the tree.

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

In an inorder traversal the node is processed between its two subtrees: everything on the left first, then the node, then everything on the right. On a binary search tree this produces the values in ascending order, which is the main reason inorder traversal is used.

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

InorderTraversal.java 
// Inorder traversal of a binary tree
public class InorderTraversal {

  static class Node {
    int data;
    Node left, right;

    Node(int data) {
      this.data = data;
    }
  }

  static void inorder(Node node) {
    if (node == null) {
      return;                              // empty subtree: nothing to visit
    }
    inorder(node.left);                    // 1. left subtree
    System.out.print(node.data + " ");     // 2. the node itself
    inorder(node.right);                   // 3. right subtree
  }

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

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

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

In a preorder traversal the node is processed before its subtrees. Because every parent appears before its children, preorder is used to copy or serialize a tree.

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

PreorderTraversal.java 
// Preorder traversal of a binary tree
public class PreorderTraversal {

  static class Node {
    int data;
    Node left, right;

    Node(int data) {
      this.data = data;
    }
  }

  static void preorder(Node node) {
    if (node == null) {
      return;                              // empty subtree: nothing to visit
    }
    System.out.print(node.data + " ");     // 1. the node itself
    preorder(node.left);                   // 2. left subtree
    preorder(node.right);                  // 3. right subtree
  }

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

    System.out.println("Preorder traversal");
    preorder(root);
    System.out.println();
  }
}
Output
Preorder traversal
40 30 20 35 60

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

In a postorder traversal the node is processed after both of its subtrees. Because children come before their parent, postorder is used to delete a tree or to evaluate an expression tree.

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

PostorderTraversal.java 
// Postorder traversal of a binary tree
public class PostorderTraversal {

  static class Node {
    int data;
    Node left, right;

    Node(int data) {
      this.data = data;
    }
  }

  static void postorder(Node node) {
    if (node == null) {
      return;                              // empty subtree: nothing to visit
    }
    postorder(node.left);                  // 1. left subtree
    postorder(node.right);                 // 2. right subtree
    System.out.print(node.data + " ");     // 3. the node itself
  }

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

    System.out.println("Postorder traversal");
    postorder(root);
    System.out.println();
  }
}
Output
Postorder traversal
20 35 30 60 40