Yet another easy trees problem doubt

1

:man_facepalming:

So i implemented this using stack and got AC, however my queue solution fails for a test case…


class Solution {
public:
   vector<int> postorder(Node* root) {
    if(root==NULL) return {};
    vector<int> res;
    queue<Node*> stk;
    stk.push(root);
    while(!stk.empty())
    {
        Node* temp=stk.front();
        stk.pop();
        for(int i=temp->children.size()-1;i>=0;i--) stk.push(temp->children[i]);
        res.push_back(temp->val);
    }
    reverse(res.begin(), res.end());
    return res;
}
};

Fails for:

Output:
[14,11,12,13,6,7,8,9,10,2,3,4,5,1]
Expected:
[2,6,14,11,7,3,12,8,4,13,9,10,5,1]

Accepted stack approach:

class Solution {
public:
   vector<int> postorder(Node* root) {
    if(root==NULL) return {};
    vector<int> res;
    stack<Node*> stk;
    stk.push(root);
    while(!stk.empty())
    {
        Node* temp=stk.top();
        stk.pop();
        for(int i=0;i<temp->children.size();i++) stk.push(temp->children[i]);
        res.push_back(temp->val);
    }
    reverse(res.begin(), res.end());
    return res;
}
};
2

Same here i also tried queue but it fails maybe because it gives level order traversal

3

It’s just a coincidence the queue solution passed for some test case because we use queue (First in First out) for a level order traversal (or a breadth-first search) and a stack (Last in First out) for a depth first search.

Go through the following links for preorder, postorder, inorder, and level order traversal of trees (iterative implementation).

Level Order - Also called BFS

All these are also called DFS:
PreOrder
Postorder
InOrder

Learning these iterative alternatives (for inorder and postorder) are not really necessary, but they might turn out to be helpful obsessionally!

4

Yes, we use stacks for these. But im not able to see why queues wont work here. I am pushing the opposite way i did for stacks

5

Well well well, if you’re pushing the children in the reverse order, a queue does not simulate a stack. You are essentially doing a level order traversal, but you’re going from right to left instead of left to right (by pushing the children in reverse order).