2.4 Traversal (iterative)

To avoid stack overflow

2.4.1 Pre-Order

Solution:

1. The root is the top element on the stack. Once the root is traversed, we can print it directly and eliminate it from stack.

2. Traverse left sub first, so the right sub should be retained in the stack before left sub is done being traversed.

public void preOrder(TreeNode root) {
  if (root == null) { return; }
  Deque<TreeNode> stack = new ArrayDeque<>();
  stack.offerFirst(root);
  while (!stack.isEmpty()) {
    TreeNode cur = stack.pollFirst();
    if (cur.right != null) {
      stack.offerFirst(cur.right);
    }
    if (cur.left != null) {
      stack.offerFirst(cur.left);
    }
  }
}

2.4.2 In-Order

Solution:

1. Cannot eliminate root from stack before traversing all the left sub. Use a helper node to store the next visiting node and subtree.

2. When the helper node is null, which means the left subtree of the root is finished, the root is the top element in the stack, then we can print the top, and push right into the helper. When the helper node is not null, which means it is the next node to be pushed into stack.

3. Stop condition: helper node is null && stack is empty.

public void inOrder(TreeNode root) {
  if (root == null) { return; }
  Deque<TreeNode> stack = new ArrayDeque<>();
  TreeNode helper = root;
  while (helper != null || !stack.isEmpty()) {
    if (helper != null) {
     stack.offerFirst(helper);
     helper = helper.left;
    } else {
      helper = stack.pollFirst();
      System.out.println(helper.key);
      helper = helper.right;
    }
  }
}

2.4.3 Post-order

Solution:

1. We could just store all the nodes before we can get the whole traversal sequence, but it takes out memory. We can maintain a previous node to record the previous visiting node on the traversing path, so that we know what direction is being taken now and next.

2. root = top element in stack

if pre == null: go down(left sub is priority)

if pre == cur.parent: go down(left sub is priority)

if pre == cur.left: go right

if pre == cur.right: pop cur, go up

public void postOrder(TreeNode root) {
  if (root == null) { return; }
  Deque<TreeNode> stack = new ArrayDeque<>();
  TreeNode pre = null;
  stack.offerFirst(root);

  while (!stack.isEmpty()) {
    TreeNode cur = stack.peekFirst();
     if (pre == null || cur == pre.left || cur == pre.right) {     //go down
       if (cur.left != null) {
         stack.offerFirst(cur.left);
       } else if (cur.right != null) {
         stack.offerFirst(cur.right);
       } else {
         System.out.println(cur.key);
         stack.pollFirst();
       }
     } else if (pre == cur.left) {		//go right from left
       if (cur.right != null) {
         stack.offerFirst(cur.right);
       } else {
          System.out.println(cur.key);
          stack.pollFirst();
       }
     } else {				//pop cur, go up
       System.out.println(cur.key);
       stack.pollFirst();
     }
     pre = cur;
   }
}