Binary Tree Traversal

Background

You must have heard of binary trees. Nothing special about it. Each node has two nodes(right and left). One of the most common interview questions is traversing the tree. There are three common types of traversals -

1. Pre Order (Root - Left - Right)
2. In Order (Left - Root - Right)
3. Post Order (Left - Right - Root)

 We are going to first write code for the data structure that forms the Node which is used further to build the tree. Node class code goes something like below

package in.blogspot.osg.Demo;

public class Node {

    private String data;
    private Node left;
    private Node right;

    public String getData() {
        return data;
    }
    public void setData(String data) {
        this.data = data;
    }
    public Node(String data){
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }
    public void setLeft(Node left) {
        this.left = left;
    }
    public Node getRight() {
        return right;
    }
    public void setRight(Node right) {
        this.right = right;
    }

}

Very simple. In this node structure we have String data and two nodes right and left. We have corresponding getters and setters. Note that data,right and left are instance variables and are assigned default values(null is our case).

Not Lets us build one tree and print various traversals.

package in.blogspot.osg.Demo;

public class MainRun {

    public static void main(String args[]){

        Node root = new Node("Aniket");

        root.setLeft(new Node("Amit"));
        root.setRight(new Node("Anubhav"));

        root.getLeft().setLeft(new Node("Sam"));
        root.getLeft().setRight(new Node("Ram"));

        root.getRight().setLeft(new Node("John"));
        root.getRight().setRight(new Node("Mark"));

        System.out.println("Printing Pre Order Traversal");
        PreOrder.printPreOrder(root);
        System.out.println("**********");
        
        System.out.println("Printing Post Order Traversal");
        PostOrder.printPostOrder(root);
        System.out.println("**********");
        
        System.out.println("Printing In Order Traversal");
        InOrder.printInOrder(root);
        System.out.println("**********");

    }

}

Above tree could be visualize as follows -

Now lets see our actual traversal logic. They are divided into 3 separate classes and each have it's own static method with corresponding logic.

Pre Order

package in.blogspot.osg.Demo;

public class PreOrder {

    /**
     * PreOrder : root-left-right
     * @param root
     */
    public static void printPreOrder(Node root){
        System.out.println("Value : " + root.getData());
        if(root.getLeft() != null){
            printPreOrder(root.getLeft());
        }
        if(root.getRight() != null){
            printPreOrder(root.getRight());
        }
    }
}

Post Order

package in.blogspot.osg.Demo;

public class PostOrder {
    
    /**
     * PostOrder : left-right-root
     * @param node
     */
    public static void printPostOrder(Node root){
       
        if(root.getLeft() != null){
            printPostOrder(root.getLeft());
        }
        if(root.getRight() != null){
            printPostOrder(root.getRight());
        }
        System.out.println("Value : " + root.getData());
    }
}

In Order

package in.blogspot.osg.Demo;

public class InOrder {
    
    /**
     * InOrder : left-root-right
     * @param root
     */
    public static void printInOrder(Node root){
        if(root.getLeft() != null){
            printInOrder(root.getLeft());
        }
        System.out.println("Value : " + root.getData());
        if(root.getRight() != null){
            printInOrder(root.getRight());
        }   
    }
}

Output for the same is

Output : 

Printing Pre Order Traversal
Value : Aniket
Value : Amit
Value : Sam
Value : Ram
Value : Anubhav
Value : John
Value : Mark
**********
Printing Post Order Traversal
Value : Sam
Value : Ram
Value : Amit
Value : John
Value : Mark
Value : Anubhav
Value : Aniket
**********
Printing In Order Traversal
Value : Sam
Value : Amit
Value : Ram
Value : Aniket
Value : John
Value : Anubhav
Value : Mark
**********

Level Order

Leaving the above three types of traversal there is one more type of traversal called level traversal in which we visit all nodes on the same level from left to right before moving on to the next level.

Code for Level traversal goes something like below - 

We need to use queue data structure for this

public class LevelTraversal {

    static Queue<Node> levelQueue = new LinkedList<Node>();

    public static void printLeveltraversal(Node root){

        System.out.println("Value : " + root.getData());

        if(root.getLeft() != null){
            levelQueue.offer(root.getLeft());
        }
        if(root.getRight() != null){
            levelQueue.offer(root.getRight());
        }

        if(levelQueue.size() != 0){
            printLeveltraversal(levelQueue.poll());
        }
    }

}

You can call this function from the same main we defined above output would be as follows

Output : 

Level order Traversal
Value : Aniket
Value : Amit
Value : Anubhav
Value : Sam
Value : Ram
Value : John
Value : Mark

You can uniquely derive the original binary tree give it's

1. Pre order and in order traversal
2. Post order and in order traversal

But you cannot determine a unique binary tree with just it's Pre ordee and  Post order traversals. However if you have the constraint that each internal node has both two children then you can very well find the original tree with above data.

Related Links

• Iterative binary tree traversal (OSFG)
• DataStructure git repository 
• Print binary tree in Spiral order (OSFG)