aqd14
3/25/2019 - 4:20 AM

Iterative post order traversal for binary tree

// node.left -> node.right -> node

public void postorder(TreeNode root) {
    
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    
    stack1.push(root);
    
    TreeNode current;
    
    while (!stack1.empty() || current != null) {
        current = stack1.pop();
        stack2.push(current);
        
        if (current.left != null) {
            stack1.push(current.left);
        }
        
        if (current.right != null) {
            stack1.push(current.right);
        }
    }
    
    while (!stack2.empty()) {
        visit(stack2.pop());
    }
}

// Using Deque in Java
public void postorder(TreeNode root) {
    
    Deque<TreeNode> deque = new Deque<>();
    
    TreeNode current = root;
    
    while (!deque.empty() || current != null) {
        if (current != null) {
            deque.addFirst(current);
            current = current.left;
        } else {
            current = deque.pop();
            visit(current);
            current = current.right;
        }
    }
}