Problem Statement

Given a binary tree, find its preorder, inorder and postorder traversals without recursion

Problem Links

Binary Tree Preorder Traversal - LeetCode

Inorder Traversal - InterviewBit

Binary Tree Postorder Traversal - LeetCode

Code

Pre Order Traverse

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.add(p.val);  // Add before going to children
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            p = node.right;
        }
    }
    return result;
}

In Order Traverse

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            result.add(node.val);  // Add after all left children
            p = node.right;
        }
    }
    return result;
}

Post Order Traverse

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        
        stack<TreeNode*> st;
       
        vector<int> res;
        
        if(!root)
            return res;
        
        while(!st.empty() || root)
        {
            if(root)
            {
                res.push_back(root->val);
                st.push(root);
                root = root->right;
            }
            else
            {
                TreeNode* node = st.top();
                
                st.pop();
                
                root = node->left;
                
            }
            
            
           
            
        }
        reverse(res.begin(),res.end());
        
        return res;
    }
};

Space Optimised solution which is O(1) - Threaded binary tree (Morris traversal)