Morris Traversal Binary Trees

vector<int> morris(TreeNode* root){

    vector<int> in;

    //two nodes: 1. for current and 2. for sub traversal 

    //i.e. for connecting threads.

    TreeNode* cur = root;

    while(cur != NULL){

        if(cur->left == NULL){

            in.push_back(cur->data);

            cur = cur->right;

        }

        else{

            //goto rightmost and create thread:

            TreeNode* prev = cur->left;

            while(prev->right && prev->right != cur){

                prev = prev->right;

            }

            //two cases arise: prev->right == null or 

            //  prev->right == cur:

            if(prev->right == NULL){

                prev->right = cur;

                cur = cur->left; //cur continues traversal.

            }

            else{

                //already thread present,

                // prev->right is at bottom:

                //cut the thread, store dataue and 

                //continue for right traversal:

                prev->right = NULL;

                in.push_back(cur->data);

                cur = cur->right;

            }

        }

    }

    return in;

}

vector<int> morrisPre(TreeNode* root){

    vector<int> pre;

    //two nodes: 1. for current and 2. for sub traversal 

    //i.e. for connecting threads.

    TreeNode* cur = root;

    while(cur != NULL){

        if(cur->left == NULL){

            pre.push_back(cur->data);

            cur = cur->right;

        }

        else{

            //goto rightmost and create thread:

            TreeNode* prev = cur->left;

            while(prev->right && prev->right != cur){

                prev = prev->right;

            }

            //two cases arise: prev->right == null 

            //or prev->right == cur:

            if(prev->right == NULL){

                prev->right = cur;

                pre.push_back(cur->data);

                cur = cur->left; //cur continues traversal.

            }

            else{

                //already thread present,

                // prev->right is at bottom:

                //cut the thread, store dataue and 

                //continue for right traversal:

                prev->right = NULL;

                cur = cur->right;

            }

        }

    }

    return pre;

}