Inorder Traversal without recursion and with space complexity O(1)


#1

vector Solution::inorderTraversal(TreeNode* A) {
vectorv;
if(!A) return v;
TreeNode* curr=A,*next;
while(curr){
if(!curr->left){
v.push_back(curr->val);
curr=curr->right;
}
else{
next=curr->left;
while(next->right!=NULL && next->right != curr)
next = next->right;
if(next->right==NULL){
next->right=curr;
curr=curr->left;
}

    else if(next->right==curr){
       next->right=NULL;
    v.push_back(curr->val);
     curr=curr->right;   
    }
    
    }
}
return v;

}