Binary Tree Traversal (Inorder, Preorder and Postorder)

In our previous post, we saw how to implement a binary search tree in Java and how to insert nodes in binary search tree.In this post, we will talk about the binary tree traversal. We will work on java code for traversing a binary tree in Java.

1. Binary Tree Traversal

Binary tree traversal differs from the linear data structure. In the linear data structure (e.g. Arrays, Linked list etc), we have only one logical way to traverse through them. We start from the beginning and move through each element. Binary tree is non-linear data structure, and it provides few different options for traversal. On a high level, we have the following 2 options for binary tree traversal in Java.

  1. Depth-First Traversal.
  2. Breadth First Search or Level Order Traversal

In this article we will focus on the binary tree traversal using depth first search.

2. Depth-First-Search

The depth-first search (DFS) is a tree traversal technique. In DFS, we go as deep as possible down to one path before we explore or visit the different node or the next sibling (It’s like a maze; you go to one end before exploring other side). Here is how the depth-first search will traverse the tree starting from root node.

Binary Tree Traversal
Depth -First Tree Traversal

If you look at the above picture, we are doing picking the one side of the tree and traversing it before going to the next side of the tree.There are few advantages of the depth-first search traversal.

  1. DFS on binary tree requires less memory than breadth-first search.
  2. It’s easy to implement (using recursion of loop).

There are three variations of the Depth-first traversal.

  1. In-order tree traversal.
  2. Preorder Tree traversal
  3. Postorder traversal

Let’s see how to implement these binary tree traversals in Java and what is the algorithm for these binary tree traversals.

2.1. Inorder Binary Tree Traversal

In the in-order binary tree traversal, we visit the left sub tree than current node and finally the right sub tree. Here is the high-level algorithm for BST in-order traversal.

1. Traverse the left sub-tree (keep visit the left sub tree until you reach leaf node).
2. Visit the current node.
3. Traverse the left sub-tree. (same as #1)

//pay attention to visit and traverse

The In order binary tree traversal will give the output in the ascending order. Therefore, we also call it in-order tree traversal.

inorder binary tree traversal

This is how we can implement the in-order binary search tree traversal in Java.

public void inOrderTraversal() {
    inOrderTraversal(root);
}

/*
 Internal private method to do in order traversal.We will pass the
 root node to start with and will visit the tree recursively using the following
 path left-current-right
*/
private void inOrderTraversal(Node node) {

    //We will continue until null or empty node is found
    if (node != null) {

        //visit the left subtree until the leaf node
        inOrderTraversal(node.left);

        //Print the node
        System.out.println(node.data);

        //process the same step for the right node
        inOrderTraversal(node.right);
    }
}

2.2. Preorder Binary Search Tree Traversal

The pre-order binary tree traversal involve visit the current node followed by left sub-tree and finally the right sub-tree. Here is a high-level algorithm for preorder BST traversal.

//Preorder BST tree traversal

1. Visit current node.
2. Traverse the left sub-tree.
3. Traverse right sub-tree.

//pay attention to visit and traverse

Here are some well-known use cases where Preorder traversal is useful.

  1. Creating a copy of the tree.
  2. To get prefix expression of an expression tree.Read polish notation for more details.
pre-order binary search tree traversal.

Here is how we can implement the in-order binary tree traversal in Java.

public void preOrderTraversal() {
    preOrderTraversal(root);
}

/*
Internal private method to do pre order traversal.We will pass the
root node to start with and will visit the tree recursively using the following
path current-left-right
*/
private void preOrderTraversal(Node node) {

    //We will continue until null or empty node is found
    if (node != null) {

        //Print the node
        System.out.println(node.data);

        //visit the left subtree until the leaf node
        inOrderTraversal(node.left);

        //process the same step for the right node
        inOrderTraversal(node.right);
    }
}

We are using recursion for these examples, you can also implement the same traversal using while loop.

2.3. Postorder Binary Tree Traversal

The post-order binary tree traversal, we traverse the left sub tree, the right sub-tree and finally visit the root node.Here is the algorithm for the post-order BST traversal.

//postorder algorithm.

1. Traverse the left sub tree.
2. Traverse the right sub tree.
3. Visit the node

in a post-order binary search tree traversal, the root is always the last node visited.

post-order binary search tree traversal

This is how we will implement the post-order traversal in binary tree in Java.

public void postOrderTraversal() {
    postOrderTraversal(root);
}

/*
Internal private method to do post-order traversal.We will pass the
root node to start with and will visit the tree recursively using the following
path right-left-current
*/
private void postOrderTraversal(Node node) {

    //We will continue until null or empty node is found
    if (node != null) {

        //visit the left subtree until the leaf node
        inOrderTraversal(node.left);

        //process the same step for the right node
        inOrderTraversal(node.right);

        //Print the node
        System.out.println(node.data);
    }
}

3. Binary Tree Traversal In Java

Here is the complete example for the binary search tree traversal (In order, Preorder and Postorder) in Java.

package com.javadevjournal.datastructure.tree.bst;


public class BinarySearchTree {

    private Node root;

    /**
     * In order BST traversal allows to traverse tree in the sorted order.
     * This traversal follow left->current-right pattern.
     * <li>left sub-tree will be viisted first.</li>
     * <li> Current node will be viisted after left traversal</li>
     * <li>Right subtree will be visited in the end.</li>
     */
    public void inOrderTraversal() {
        inOrderTraversal(root);
    }

    public void postOrderTraversal() {
        postOrderTraversal(root);
    }

    public void preOrderTraversal() {
        preOrderTraversal(root);
    }


    /*
     Internal private method to do in order traversal.We will pass the
     root node to start with and will visit the tree recursively using the following
     path left-current-right
    */
    private void inOrderTraversal(Node node) {

        //We will continue until null or empty node is found
        if (node != null) {

            //visit the left subtree until the leaf node
            inOrderTraversal(node.left);

            //Print the node
            System.out.println(node.data);

            //process the same step for the right node
            inOrderTraversal(node.right);
        }
    }


    /*
     Internal private method to do pre order traversal.We will pass the
     root node to start with and will visit the tree recursively using the following
     path current-left-right
    */
    private void preOrderTraversal(Node node) {

        //We will continue until null or empty node is found
        if (node != null) {

            //Print the node
            System.out.println(node.data);

            //visit the left subtree until the leaf node
            inOrderTraversal(node.left);

            //process the same step for the right node
            inOrderTraversal(node.right);
        }
    }


    /*
     Internal private method to do post-order traversal.We will pass the
     root node to start with and will visit the tree recursively using the following
     path right-left-current
    */
    private void postOrderTraversal(Node node) {

        //We will continue until null or empty node is found
        if (node != null) {

            //visit the left subtree until the leaf node
            inOrderTraversal(node.left);

            //process the same step for the right node
            inOrderTraversal(node.right);

            //Print the node
            System.out.println(node.data);
        }
    }

    /**
     * Internal node class representing the node of the BST. This contains the following information
     * <li>data- actual data stored in the Tree</li>
     * <li>left - Left child of the node</li>
     * <li>right - right child of the node</li>
     */
    class Node {

        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
            //this just for reading.they will be null by default
            this.left = null;
            this.right = null;
        }
    }
}

// Main program to test it
package com.javadevjournal.datastructure.tree;

import com.javadevjournal.datastructure.tree.bst.BinarySearchTree;

public class BinarySearchTreeTest {

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        /* We are building a BST as below
             52
           /    \
          15     56
         /  \    /  \
        9    16 54   61
       / \
      3   10 */

        bst.insert(52);
        bst.insert(15);
        bst.insert(56);
        bst.insert(9);
        bst.insert(16);
        bst.insert(54);
        bst.insert(3);
        bst.insert(10);
        bst.insert(61);

        //inorder traversal
        bst.inOrderTraversal(); //output [3,9,10,15,16,52,54,56,61]

        //pre-order
        bst.preOrderTraversal(); //output [52,15,9,3,10,16,56,54,61]

        //post-order
        bst.postOrderTraversal(); //output [3,10,9,16,15,54,61,56,52]
    }
}

Summary

In this article, we saw the binary tree traversal and how to implement the binary search tree traversal in Java. We covered the depth-first-search and how to perform in-order, preorder and post-order traversal. As always, the source code is available on GitHub.

1 Comment
Newest
Oldest Most Voted
Inline Feedbacks
View all comments