Leetcode:Binary Tree Inorder Traversal.problem:Memory Limited exceeded

Question

The following code performs a binarytree inorder traversal. When I execute it in Leetcode, I receive a Run Status Code: Memory Limit Exceeded. Could someone explain what is causing this error?

   vector<int> inorderTraversal(TreeNode* root) {

    vector<int> res;
    if(root==NULL)
        return res;
    stack<TreeNode*> st;
    st.push(root);
    while(st.empty()==0){
        TreeNode* cur=st.top();
        st.pop();
        if(cur->right!=NULL)//right childtree is not NULL,push
            st.push(cur->right);
        if(cur->left!=NULL){//left childtree is not NULL,push
            st.push(cur);
            st.push(cur->left);
        }
        else       //if left child tree is NULL,store the value
            res.push_back(cur->val);

    }

    //inorder(root,res);
    return res;
}

Answer 1

Your code only stores a value into the result stack if the left child node is a null.

However, for your example, node 2 left child node is never set to a null and hence it is never inserted into the result stack but it is in the st stack. If you print out your output, you can observe that 3 is inserted in a loop, hence causing a memory issue.

A possible strategy to keep track of the ancestor:

• Check for trivial case.
• Prepare a stack to keep the ancestors, and one to keep the result.
• While the stack is non-empty or if the root is not null
  • if the root is not null:
    • insert the root onto the ancestor stack.
    • update the root to be the left child of the root, possibly to be null.
  • if the root is null (meaning dead end from the left)
    • visit the stack, pop the top element to be the root.
    • add the root to the result stack
    • assign the right child of the root to be the root, possibly to be a null.