c++binary-treeinorder

I am getting segmentation fault while using Morris algorithm for inorder traversal of a binary tree


The question link was this: Inorder Traversal (GFG) I referred the geeksforgeeks article that had the same code but in void function. I modified it to fit the question. Now I am getting segmentaion fault and I don't know why. The GFG article: Inorder Tree Traversal without recursion and without stack!

vector<int> inOrder(Node* root) {
    // Your code here
    vector<int>ans;
    Node* current = root;
    Node* pre;
    
    if(!root){return ans;}
    
    while(current){
        if(!root->left){
            ans.push_back(current->data);
            current = current->right;
        }
        else{
            pre = current->left;
            while(pre->right && (pre->right != current)){pre = pre->right;}
            if(!pre->right){
                pre->right = current;
                current = current->left;
            }
            else{
                pre->right = NULL;
                ans.push_back(current->data);
                current = current->right;
            }
        }
    }
    return ans;
}

Solution

  • The following condition is wrong:

    if(!root->left){
    

    This will make the same check in each iteration. It should relate to the current node:

    if(!current->left){