TREE TRAVERSAL CODE

JAVA PYTHON GO KOTLIN C# RUBY C++ Java Script

Example :

class Node {
    String data;
    Node left;
    Node right;

    public Node(String value) {
        data = value;
        left = null;
    	right = null;
    }
}

public class TreeTraversal {

    Node root;

    TreeTraversal() {
        root = null;
    }

    void preorder(Node node) {

        if (node != null) {

            System.out.print(node.data + "  ");
            preorder(node.left);
            preorder(node.right);
        }
    }

    void postorder(Node node) {

        if (node != null) {

            postorder(node.left);
            postorder(node.right);
            System.out.print(node.data + "  ");
        }
    }

    void inorder(Node node) {

        if (node != null) {

           inorder(node.left);
           System.out.print(node.data + "  ");
           inorder(node.right);
        }
    }

    public static void main(String[] args) {
        
        TreeTraversal treeTraversal = new TreeTraversal();
        
        treeTraversal.root = new Node("A");
        treeTraversal.root.left = new Node("B");
        treeTraversal.root.right = new Node("C");
        treeTraversal.root.left.right = new Node("D");
        treeTraversal.root.right.left = new Node("E");

        System.out.println("Preorder traversal : ");
        treeTraversal.preorder(treeTraversal.root);

        System.out.println("\n");

        System.out.println("Postorder traversal : ");
        treeTraversal.postorder(treeTraversal.root);

        System.out.println("\n");

        System.out.println("Inorder traversal : ");
        treeTraversal.inorder(treeTraversal.root);

    }
}

Output :

Preorder traversal :
A B D C E

Postorder traversal :
D B E C A

Inorder traversal :
B D A E C

So, in this case we have taken the below Tree and and calculated the Preorder, Postorder and Inorder Traversal for the below Tree.

Code Explanation for Tree Traversal

Just remember, we have used a process called 'Recursion'. Where Java maintains an internal Stack to remember the visited Nodes. So, that the Nodes are not visited twice.

So, we have a 'Node' class,

class Node {
    String data;
    Node left;
    Node right;

    public Node(String value) {
        data = value;
        left = null;
    	right = null;
    }
}

To understand the 'Node' class, let us take any 'Node' and understand it in detail.

Let us take the Node 'A' as example.

So, the Node 'A' has a name i.e 'A'. A Left part that should hold the Left Node i.e. 'B' and a Right part to hold the Right Node i.e. 'C'.

Now, if you look at the 'Node' class. It has 'String' type attribute 'String data' to hold name of the Node i.e. 'A'.

There is also a 'Node' type attribue 'Node left' that holds the left Node of 'A', i.e. 'B' and there is a 'Node' type attribue 'Node right' that holds the right Node of 'A', i.e. 'C'.

So, Node 'A' looks somewhat like,

Now, let us see the Tree Traversal in action.

So, at first we construct the Tree,

treeTraversal.root = new Node("A");
treeTraversal.root.left = new Node("B");
treeTraversal.root.right = new Node("C");
treeTraversal.root.left.right = new Node("D");
treeTraversal.root.right.left = new Node("E");

And there is the constructor in the 'Node' class that helps us create the Nodes.

public Node(String value) {
    data = value;
    left = null;
    right = null;
}

And the tree is constructed,

Next, we start the Preorder Traversal,

treeTraversal.preorder(treeTraversal.root);

And the 'preorder(Node node)' method is called, and just remember that we are passing the root Node to the method.

void preorder(Node node) {

    if (node != null) {

        System.out.print(node.data + "  ");
        preorder(node.left);
        preorder(node.right);
    }
}

Although, the lines of code looks very less. It is because, the recursion process is doing a lot for us. And it all happens internally, hidden from us.

Let us understand the process in detail.

So, the root Node is 'A' and the 'node' variable has the details of Node A in it.

In the first line we perform a 'null' check

if (node != null)

And then begin the Preorder Traversal. And the rule is 'Root --> Left --> Right'.

i.e. We visit the root element first, then visit all the elements of the Left Sub-Tree and finally, visit all the elements of the Right Sub-Tree.

So, as per the rule we will visit the root Node 'A' and print it first.

System.out.print(node.data + "  ");

So, the result is :

Then we are suppose to visit all the elements of the Left Sub-Tree. And thus we call the 'preorder(...)' method from itself, by passing the Left Node i.e. 'B' (As 'node.left' contains 'B').

preorder(node.left);

Now, the 'preorder(...)' method is called again. And this time Node 'B' becomes the new root element.

And once again the same method is executed with Node 'B'.

void preorder(Node node) {

    if (node != null) {

        System.out.print(node.data + "  ");
        preorder(node.left);
        preorder(node.right);
    }
}

Even in this case, as per the Preorder traversal process 'Root --> Left --> Right'. We print the new root element 'B'.

System.out.print(node.data + "  ");

So, the result is :

A B

And once again we call the 'preorder(...)' method.

preorder(node.left);

And this time 'node.left' is 'null'. Because 'B' has no left element.

So, 'preorder(...)' method is called with the new root element as 'null'.

void preorder(Node node) {

    if (node != null) {

        System.out.print(node.data + "  ");
        preorder(node.left);
        preorder(node.right);
    }
}

And this time 'node' variable is 'null'. So, the method execution ends here.

if (node != null)

But ! Just Hold on !

The program execution has not yet ended. This is the time when java starts 'backtracking'.

Don't get scared by the word 'backtracking'. We will understand it eventually.

Now, just think ! The method execution in the above case was not completed. i.e. The line 'preorder(node.right)' never got executed. Well ! Java also remembers it.

And Java does a time travel and goes back to the time when the method executed with Node 'B'.

void preorder(Node node) {

    if (node != null) {

        System.out.print(node.data + "  ");
        preorder(node.left);
        preorder(node.right);
    }
}

And executes the unfinished line,

preorder(node.right);

And this time 'preOrder(...)' method is called with Node 'D'.

And same way, Node 'D' would be printed.

System.out.print(node.data + "  ");

So, the result is :

A B D

And since, there are no children of Node 'D'. It is time to complete the unfinished execution, i.e. When Node 'A' was the root element.

void preorder(Node node) {

    if (node != null) {

        System.out.print(node.data + "  ");
        preorder(node.left);
        preorder(node.right);
    }
}

And we come to the unfinished line of 'preorder(...)' method.

i.e.

preorder(node.right);

And think logically, we are done with the root element 'A'. Also we are done traversing all the elements of the Left Sub-Tree 'B'. And now, it's time for us to traverse the Right Sub-Tree 'C'.

So, this time the method 'preorder(...)' is called with the root Node 'C'.

void preorder(Node node) {

    if (node != null) {

        System.out.print(node.data + "  ");
        preorder(node.left);
        preorder(node.right);
    }
}

Since the root Node is 'C'. So, we print 'C'.

System.out.print(node.data + "  ");

So, the result is :

A B D C

Then the 'preOrder(...)' method is called with 'E' as root(Since, 'E' is the left child of 'C').

preorder(node.left);

And the method is called again printing 'C'.

A B D C E

And finally, all the elements are visited and with this we complete the Preorder traversal.

And exactly the same execution pattern follows for the methods :

void postorder(Node node)
void inorder(Node node)

❮❮ PREV NEXT ❯❯