Tree Traversals - DFS - JAVA

Depth First Traversals:

Inorder Traversal:

Algorithm Inorder(tree) 

 1. Traverse the left subtree, i.e., call Inorder(left-subtree) 

 2. Visit the root. 

 3. Traverse the right subtree, i.e., call Inorder(right-subtree) 

Preorder Traversal:

Algorithm Preorder(tree) 

1. Visit the root. 

2. Traverse the left subtree, i.e., call Preorder(left-subtree) 

3. Traverse the right subtree, i.e., call Preorder(right-subtree)

Postorder Traversal:

Algorithm Postorder(tree) 

1. Traverse the left subtree, i.e., call Postorder(left-subtree) 

2. Traverse the right subtree, i.e., call Postorder(right-subtree) 

3. Visit the root.

Time Complexity: O(n)

// Java program for different tree traversals

 

/* Class containing left and right child of current

   node and key value*/

class Node

{

    int key;

    Node left, right;

 

    public Node(int item)

    {

        key = item;

        left = right = null;

    }

}

 

class BinaryTree

{

    // Root of Binary Tree

    Node root;

 

    BinaryTree()

    {

        root = null;

    }

 /* Given a binary tree, print its nodes according to the

      "bottom-up" postorder traversal. */

    void printPostorder(Node node)

    {

        if (node == null)

            return;

 

        // first recur on left subtree

        printPostorder(node.left);

 

        // then recur on right subtree

        printPostorder(node.right);

 

        // now deal with the node

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

    }

 

    /* Given a binary tree, print its nodes in inorder*/

    void printInorder(Node node)

    {

        if (node == null)

            return;

 

        /* first recur on left child */

        printInorder(node.left);

 

        /* then print the data of node */

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

 

        /* now recur on right child */

        printInorder(node.right);

    }

 

    /* Given a binary tree, print its nodes in preorder*/

    void printPreorder(Node node)

    {

        if (node == null)

            return;

 

        /* first print data of node */

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

 

        /* then recur on left sutree */

        printPreorder(node.left);

 

        /* now recur on right subtree */

        printPreorder(node.right);

    }

// Wrappers over above recursive functions

    void printPostorder()  {     printPostorder(root);  }

    void printInorder()    {     printInorder(root);   }

    void printPreorder()   {     printPreorder(root);  }

 

    // Driver method

    public static void main(String[] args)

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

 

        System.out.println("Preorder traversal of binary tree is ");

        tree.printPreorder();

 

        System.out.println("\nInorder traversal of binary tree is ");

        tree.printInorder();

 

        System.out.println("\nPostorder traversal of binary tree is ");

        tree.printPostorder();

    }

}




Output:




Preorder traversal of binary tree is
1 2 4 5 3 
Inorder traversal of binary tree is
4 2 5 1 3 
Postorder traversal of binary tree is
4 5 2 3 1