Getting a TLE in iterativePreOrder Travesrsal of a tree


  • 0
    A
    • I have maintained a stack containing the address of nodes and two
      bool values to indicate that whether left and right subtrees are
      visited or not.
    • Whenever i push a node in the stack i also push its value in the ans
      vector.
    • I compiled the same code on my compiler and in the output it shows
      bad alloc
    • Please Help me figure out my error!!

    Here's the code :

     class data {
    public:
        TreeNode *temp;
        bool leftVisited,rightVisited;
        data(TreeNode *x){
            temp=x;
            leftVisited=false;
            rightVisited=false;
            if(!temp->left){
                leftVisited=true;
            }
            if(!temp->right){
                rightVisited=true;
            }
        }
    };
    
    class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
            vector<int> ans;
            if(!root){
                return ans;
            }
            stack<data> buffer;
            data obj1(root);
            buffer.push(obj1);
            ans.push_back(root->val);
            while(!buffer.empty()){
                data current=buffer.top();
                if(current.leftVisited && current.rightVisited){
                    buffer.pop();
                }else if(!current.leftVisited && !current.rightVisited){
                    if(current.temp->left){
                        data obj(current.temp->left);
                        current.leftVisited=true;
                        buffer.push(obj);
                        ans.push_back(obj.temp->val);
                    }else if(current.temp->right){
                        data obj(current.temp->right);
                        current.rightVisited=true;
                        buffer.push(obj);
                        ans.push_back(obj.temp->val);
                    }
                }else if(!current.rightVisited){
                    if(current.temp->right){
                        data obj(current.temp->right);
                        current.rightVisited=true;
                        buffer.push(obj);
                        ans.push_back(obj.temp->val);
                    }
                }
            }
            return ans;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.