Tree traversal notes

1. Inorder:

- travel left subtree in inorder
- visit root
- travel right subtree in inorder

Recursive approach:

void inOrder() {
 if(root != null) {
  inOrder(root.left);
  System.out.println(root.data);
  inOrder(root.right);
 }
}

Iterative approach using stacks:

void inOrder() {

    Stack stack = new Stack();

    Node current = root;

    while(current!=null || !stack.isEmpty()) {
        //push to stack and move to left sub-tree
        if(current!=null){
            stack.push(current);
            current = current.left;
        }
        else { //we need to pop out nodes from stack and shift to its right sub-tree
            current = stack.pop(); //visited node
            System.out.println(current.data);
            current = current.right;
        }
    }
}

2. Pre-order:

- visit root
- travel left subtree in preorder
- travel right subtree in preorder

Recursive approach:

void preOrder() {
    if(root != null) {
        System.out.println(root.data);
        preOrder(root.left);
        preOrder(root.right);
    }
}

Iterative approach using stacks:

void inOrder() {

    Stack stack = new Stack();

    Node current = root;

    while(current!=null || !stack.isEmpty()) {
        //print each value, then push its right subtree to stack and move to left subtree
        if(current!=null){
            System.out.println(current.data); //visited node
            stack.push(current.right); //push right subtree
            current = current.left; //shift to left subtree
        }
        else {
            current = stack.pop();
        }
    }
}