Tree traversals Recursive and Iterative

Tree traversals

// Java program for inorder, preorder, postorder and levelorder tree traversals both recursive and iterative.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.ArrayList;

/* 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 printPostorderRecursive(Node node) {
    if (node == null)
      return;

    // first recur on left subtree
    printPostorderRecursive(node.left);

    // then recur on right subtree
    printPostorderRecursive(node.right);

    // now deal with the node
    System.out.print(node.key + " ");
  }

  static Stack<Node> s1, s2;

  void printPostorderIterative2Stack(Node root) {
    // Create two stacks
    s1 = new Stack<>();
    s2 = new Stack<>();

    if (root == null)
      return;

    // push root to first stack
    s1.push(root);

    // Run while first stack is not empty
    while (!s1.isEmpty()) {
      // Pop an item from s1 and push it to s2
      Node temp = s1.pop();
      s2.push(temp);

      // Push left and right children of
      // removed item to s1
      if (temp.left != null)
        s1.push(temp.left);
      if (temp.right != null)
        s1.push(temp.right);
    }

    // Print all elements of second stack
    while (!s2.isEmpty()) {
      Node temp = s2.pop();
      System.out.print(temp.key + " ");
    }
  }

  ArrayList<Integer> list = new ArrayList<Integer>();

  // An iterative function to do postorder traversal
  // of a given binary tree
  ArrayList<Integer> printPostorderIterative1Stack(Node node) {
    Stack<Node> S = new Stack<Node>();

    // Check for empty tree
    if (node == null)
      return list;
    S.push(node);
    Node prev = null;
    while (!S.isEmpty()) {
      Node current = S.peek();

      /*
       * go down the tree in search of a leaf an if so process it and pop stack
       * otherwise move down
       */
      if (prev == null || prev.left == current || prev.right == current) {
        if (current.left != null)
          S.push(current.left);
        else if (current.right != null)
          S.push(current.right);
        else {
          S.pop();
          list.add(current.key);
        }

        /*
         * go up the tree from left node, if the child is right push it onto stack
         * otherwise process parent and pop stack
         */
      } else if (current.left == prev) {
        if (current.right != null)
          S.push(current.right);
        else {
          S.pop();
          list.add(current.key);
        }

        /*
         * go up the tree from right node and after coming back from right node process
         * parent and pop stack
         */
      } else if (current.right == prev) {
        S.pop();
        list.add(current.key);
      }

      prev = current;
    }

    return list;
  }




  /* Given a binary tree, print its nodes in inorder */
  void printInorderRecursive(Node node) {
    if (node == null)
      return;

    /* first recur on left child */
    printInorderRecursive(node.left);

    /* then print the data of node */
    System.out.print(node.key + " ");

    /* now recur on right child */
    printInorderRecursive(node.right);
  }

  void printInorderIterative() {
    if (root == null)
      return;

    Stack<Node> s = new Stack<Node>();
    Node curr = root;

    // traverse the tree
    while (curr != null || s.size() > 0) {

      /*
       * Reach the left most Node of the curr Node
       */
      while (curr != null) {
        /*
         * place pointer to a tree node on the stack before traversing the node's left
         * subtree
         */
        s.push(curr);
        curr = curr.left;
      }

      /* Current must be NULL at this point */
      curr = s.pop();

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

      /*
       * we have visited the node and its left subtree. Now, it's right subtree's turn
       */
      curr = curr.right;
    }
  }




  /* Given a binary tree, print its nodes in preorder */
  void printPreorderRecursive(Node node) {
    if (node == null)
      return;

    /* first print data of node */
    System.out.print(node.key + " ");

    /* then recur on left subtree */
    printPreorderRecursive(node.left);

    /* now recur on right subtree */
    printPreorderRecursive(node.right);
  }

  void printPreorderIterative(Node node) {

    // Base Case
    if (node == null) {
      return;
    }

    // Create an empty stack and push root to it
    Stack<Node> nodeStack = new Stack<Node>();
    nodeStack.push(root);

    /*
     * Pop all items one by one. Do following for every popped item a) print it b)
     * push its right child c) push its left child Note that right child is pushed
     * first so that left is processed first
     */
    while (nodeStack.empty() == false) {

      // Pop the top item from stack and print it
      Node mynode = nodeStack.peek();
      System.out.print(mynode.key + " ");
      nodeStack.pop();

      // Push right and left children of the popped node to stack
      if (mynode.right != null) {
        nodeStack.push(mynode.right);
      }
      if (mynode.left != null) {
        nodeStack.push(mynode.left);
      }
    }
  }



  /* Given a binary tree, print its nodes in levelorder */
  void printLevelOrderRecursive() {
    int h = height(root);
    int i;
    for (i = 1; i <= h; i++)
      printCurrentLevel(root, i);
  }

  /*
   * Compute the "height" of a tree -- the number of nodes along the longest path
   * from the root node down to the farthest leaf node.
   */
  int height(Node root) {
    if (root == null)
      return 0;
    else {
      /* compute height of each subtree */
      int lheight = height(root.left);
      int rheight = height(root.right);

      /* use the larger one */
      if (lheight > rheight)
        return (lheight + 1);
      else
        return (rheight + 1);
    }
  }

  void printCurrentLevel(Node root, int level) {
    if (root == null)
      return;
    if (level == 1)
      System.out.print(root.key + " ");
    else if (level > 1) {
      printCurrentLevel(root.left, level - 1);
      printCurrentLevel(root.right, level - 1);
    }
  }

  /* Given a binary tree, print its nodes in levelorder using a queue */
  void printLevelOrderIterative() {
    Queue<Node> queue = new LinkedList<Node>();
    queue.add(root);
    while (!queue.isEmpty()) {

      /*
       * poll() removes the present head. For more information on poll() visit
       * http://www.tutorialspoint.com/java/ util/linkedlist_poll.htm
       */
      Node tempNode = queue.poll();
      System.out.print(tempNode.key + " ");

      /* Enqueue left child */
      if (tempNode.left != null) {
        queue.add(tempNode.left);
      }

      /* Enqueue right child */
      if (tempNode.right != null) {
        queue.add(tempNode.right);
      }
    }
  }

  // Wrappers over above recursive functions
  void printPostorderRecursive() {
    printPostorderRecursive(root);
  }

  void printPostorderIterative2Stack() {
    printPostorderIterative2Stack(root);
  }

  void printInorderRecursive() {
    printInorderRecursive(root);
  }

  void printPreorderRecursive() {
    printPreorderRecursive(root);
  }

  void printPreorderIterative() {
    printPreorderIterative(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);
    tree.root.right.left = new Node(6);
    tree.root.right.right = new Node(7);

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

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

    System.out.println("\nRecursive Inorder traversal of binary tree is ");
    tree.printInorderRecursive();

    System.out.println("\nIterative Inorder traversal of binary tree is ");
    tree.printInorderIterative();

    System.out.println("\nRecursive Postorder traversal of binary tree is ");
    tree.printPostorderRecursive();

    System.out.println("\nIterative Postorder traversal using 2 stacks of binary tree is ");
    tree.printPostorderIterative2Stack();

    System.out.println("\nIterative Postorder traversal using 1 stacks of binary tree is ");
    ArrayList<Integer> mylist = tree.printPostorderIterative1Stack(tree.root);
    for (Integer node : mylist)
      System.out.print(node + " ");

    System.out.println("\nRecursive Level order traversal of binary tree is ");
    tree.printLevelOrderRecursive();

    System.out.println("\nIterative Level order traversal of binary tree using a queue is ");
    tree.printLevelOrderIterative();

  }
}

Output:

Recursive Preorder traversal of binary tree is 
1 2 4 5 3 6 7 
Iterative Preorder traversal of binary tree is 
1 2 4 5 3 6 7 
Recursive Inorder traversal of binary tree is 
4 2 5 1 6 3 7 
Iterative Inorder traversal of binary tree is 
4 2 5 1 6 3 7 
Recursive Postorder traversal of binary tree is 
4 5 2 6 7 3 1 
Iterative Postorder traversal using 2 stacks of binary tree is 
4 5 2 6 7 3 1 
Iterative Postorder traversal using 1 stacks of binary tree is 
4 5 2 6 7 3 1 
Recursive Level order traversal of binary tree is 
1 2 3 4 5 6 7 
Iterative Level order traversal of binary tree using a queue is 
1 2 3 4 5 6 7