Binary Tree Traversals (Inorder, Preorder and Postorder)

What is Binary Tree?

Each node of the tree has at most two children - a left and a right child.

Complete Binary Tree

All the levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible.

Perfect Binary Tree

A binary tree of height h having the maximum number of nodes is a perfect binary tree.

Full Binary Tree

A full Binary tree is a special type of binary tree in which every parent node/internal node has either two or no children. It is also known as a proper binary tree.

Tree Traversal

Iterative Preorder Traversal

public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> results = new ArrayList<>();
        if(root==null) return results;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        //when it comes to the last node, stack will be empty
        while(!stack.empty()){
            TreeNode cur = stack.pop();
            results.add(cur.val);
            if(cur.right!=null)
                stack.push(cur.right);
            if(cur.left!=null)
                stack.push(cur.left);
        }

        return results;
    }

Iterative Inorder Traversal

public static List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    TreeNode cur = root;
    Stack<TreeNode> stack = new Stack<>();
    while(cur!=null || !stack.empty()){
        //left
        while(cur!=null){
            stack.push(cur);
            cur = cur.left;
        }
        //root and right
        if(!stack.empty()){
            cur = stack.pop();
            res.add(cur.val);
            cur = cur.right;
        }
    }
    return res;
}

Iterative Postorder Traversal

//postorder traversal:-> right, left, root
public List<Integer> postorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> res = new ArrayList<>();
    TreeNode cur = root;
    TreeNode prev = null;
    while(cur!=null || !stack.empty()){
        while(cur!=null){
            stack.push(cur);
            cur=cur.left;
        }
        if(!stack.empty()){
            cur = stack.pop();
            if(cur.right!=null && prev!=cur.right){
                stack.push(cur);
                cur=cur.right;
            }else{
                res.add(cur.val);
                prev=cur;
                cur=null;
            }
        }
    }
    return res;
}