Traversal of Binary tree using Recursion- Algo 10

Binary Tree Traversal – Traversal of Binary tree using Recursion

Unlike Linear Data structure, Trees can be traversed in multiple ways.

     1)    Depth First Traversals

a)     InOrder (L-D-R)

b)    PreOrder (D-L-R)

c)     PostOrder (L-R-D)

    2)    Breadth first or Level order Traversal

     Implementation of a Node

public class Node {

          int data;

         Node left, right;

      

         Node(int item) {

             data = item;

             left = right = null;

         }

}

Implementation of Binary tree traversal using Recursion

public class BinaryTreeTraversal {

     Node root;

     public static void main(String[] args) {

          BinaryTreeTraversal tree = new BinaryTreeTraversal();

          tree.root = new Node(25);

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

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

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

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

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

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

          System.out.println("Print InOrder (Left-Root-Right)");

          tree.printInOrder();

          System.out.println("\n\n"+"Print PreOrder(Root-Left-Right)");

          tree.printPreOrder();

          System.out.println("\n\n"+"Print PostOrder(Left-Right-Root)");

          tree.printPostOrder();

     }

     void printInOrder() {

          printInOrder(root);

     }

     void printPreOrder() {

          printPreOrder(root);

     }

     void printPostOrder() {

          printPostOrder(root);

     }

     // Left - Root- Right --> Inorder Traversal using Recursion

     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.data + " ");

          /* now recur on right child */

          printInOrder(node.right);

     }

     // Root- Left- Right --> Preorder Traversal using Recursion

     void printPreOrder(Node node) {

          if (node == null)

              return;

          /* first print the data of node */

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

          /* then recur on left subree */

          printPreOrder(node.left);

          /* now recur on right child */

          printPreOrder(node.right);

     }

     // Left- Right- Root --> Preorder Traversal using Recursion

     void printPostOrder(Node node) {

          if (node == null)

              return;

          /* first recur on left subtree */

          printPostOrder(node.left);

          /* then recur on left subtree */

          printPostOrder(node.right);

          /* now print data of node */

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

     }

}

Output:

Print InOrder (Left-Root-Right)

7 15 20 25 30 35 50

Print PreOrder(Root-Left-Right)

25 15 7 20 35 30 50

Print PostOrder(Left-Right-Root)

7 20 15 30 50 35 25