Tree Traversal

EPI Solution: http://elementsofprogramminginterviews.com/solutions/

Also check Binary Tree Postorder

Implement an inorder traversal with O(1) space InorderTraversalWithParentTemplate.java

  public static <T> void inOrderTraversal(BinaryTree<T> r) {

    // Empty tree.

    if (r == null) {

      return;

    }

    BinaryTree<T> prev = null, curr = r, next;

    while (curr != null) {

      if (prev == null || prev.getLeft() == curr || prev.getRight() == curr) {

        if (curr.getLeft() != null) {

          next = curr.getLeft();

        } else {

          System.out.println(curr.getData());

          next = (curr.getRight() != null ? curr.getRight() : curr.getParent());

        }

      } else if (curr.getLeft() == prev) {

        System.out.println(curr.getData());

        next = (curr.getRight() != null ? curr.getRight() : curr.getParent());

      } else {

        next = curr.getParent();

      }

      prev = curr;

      curr = next;

    }

  }

Implement preorder and postorder traversals without recursion

BinaryTreePreorderTraversalIterative.java 
  public static List<Integer> preOrderTraversal(
      final BinaryTree<Integer> root) {
    if (root == null) {
      return Collections.emptyList();
    }

    LinkedList<BinaryTree<Integer>> s = new LinkedList<>();
    s.push(root);
    List<Integer> res = new ArrayList<>();
    while (!s.isEmpty()) {
      BinaryTree<Integer> curr = s.pop();
      res.add(curr.getData());
      if (curr.getRight() != null) {
        s.push(curr.getRight());
      }
      if (curr.getLeft() != null) {
        s.push(curr.getLeft());
      }
    }
    return res;
  }
BinaryTreePostorderTraversalIterativeAlternative.jav
  public static List<Integer> postOrderTraversal(BinaryTree<Integer> root) {
    List<Integer> invPreRes = invertedPreOrderTraversal(root);
    Collections.reverse(invPreRes);
    return invPreRes;
  }

  private static List<Integer> invertedPreOrderTraversal(
      final BinaryTree<Integer> root) {
    if (root == null) {
      return Collections.emptyList();
    }

    LinkedList<BinaryTree<Integer>> s = new LinkedList<>();
    s.push(root);
    List<Integer> res = new ArrayList<>();
    while (!s.isEmpty()) {
      BinaryTree<Integer> curr = s.pop();
      res.add(curr.getData());
      if (curr.getLeft() != null) {
        s.push(curr.getLeft());
      }
      if (curr.getRight() != null) {
        s.push(curr.getRight());
      }
    }
    return res;
  }
BinaryTreePostorderTraversalIterative.java
  public static List<Integer> postOrderTraversal(
      final BinaryTree<Integer> root) {
    if (root == null) { // Empty tree.
      return Collections.emptyList();
    }

    LinkedList<BinaryTree<Integer>> s = new LinkedList<>();
    BinaryTree<Integer> prev = null;
    s.push(root);
    List<Integer> res = new ArrayList<>();
    while (!s.isEmpty()) {
      BinaryTree<Integer> curr = s.peek();
      if (prev == null || prev.getLeft() == curr || prev.getRight() == curr) {
        // Going down.
        if (curr.getLeft() != null) { // Visit left.
          s.push(curr.getLeft());
        } else if (curr.getRight() != null) { // Visit right.
          s.push(curr.getRight());
        } else { // Leaf node, then process current node.
          res.add(curr.getData());
          s.pop();
        }
      } else if (curr.getLeft() == prev) {
        // Going up, finished visiting left.
        if (curr.getRight() != null) { // Visit right.
          s.push(curr.getRight());
        } else { // No right child, then process current node.
          res.add(curr.getData());
          s.pop();
        }
      } else { // curr->right.get() == prev.
        // Going up, finished visiting left and right.
        res.add(curr.getData());
        s.pop();
      }
      prev = curr;
    }
    return res;
  }