Simple Solution Using Stacks


#1
// Preorder Traversal Using stack
public ArrayList<Integer> preorderTraversal(TreeNode A) {
    if(A==null){
        return new ArrayList<>();
    }
    ArrayList<Integer> res = new ArrayList<>();
    Stack<TreeNode> st = new Stack<>();

    st.push(A);

    while(st.size()>0){
        TreeNode node = st.pop();
        res.add(node.val);
        if(node.right!=null){
            st.push(node.right);
        }
        if(node.left!=null){
            st.push(node.left);
        }
    }

    return res ;

}

#2

how pushing right first in preorder gives us right answer …mindfucked !


#3

in preorder, we process left first . In this case we push right then left ,so that left gets processed first(Since we use Stack).


#4

Why can’t we use a queue here and like push the left first and then the right. All the other things same. I am getting wrong answer for that. I mean like for every node we are taking the root and then the left and right and pushing them in that order. It should work na even with the queue. Anyone help if you get it.


#5

We can’t use a queue here because insertion in queue happens at the back and you are only able to access the front element. I believe doubly-ended queue can be used but the use of stack is highly intuitive.