Postorder Iterative Traversal of Binary Tree Run Time Error

Question

I was doing some LeetCode questions (new at LeetCode) and I wrote a solution for traversing a binary tree iteratively. I used a stack, and I believe my logic works, but LeetCode is giving me a run time error. How can I fix this?

Here is my code:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        TreeNode* temp = root; 
        vector<int> v; 
        stack<TreeNode*> s; 

        if (temp == NULL)
            return v; 
        while (true){
            while (temp != NULL){
                if (temp->right)
                    s.push(temp->right); 
                s.push(temp); 
                temp = temp->left; 

            }
            if (s.empty())
                break; 
            temp = s.top();
            s.pop(); 
            if (s.top() == temp->right){
                s.pop(); 
                s.push(temp); 
                temp = temp->right;                 

            }else{
                v.push_back(temp->val); 
                temp = NULL; 
            }
        }
        return v; 

    }
};

Please help, thanks!

Answer 1

Your code is crashing here when you only have one item left in the stack:

temp = s.top();               // remove the last item from the stack
s.pop();                      // empty the stack
if (s.top() == temp->right){  // attempt to access the top of the stack.. boom!

The fix is to test for an empty stack before checking top:

if (!s.empty() && s.top() == temp->right) {