Simple Morris traversal, C++ , average O(1) time and O(1) space .


  • 0

    Total time complexity of traversing n nodes is O(3 * n), so average time complexity of each call is O(1). A pointer TreeNode* nextp is used to indicate next smallest node. According to morris traversal algorithm if the right children of the predecessor of nextp equal to nextp, that means the left side of nextp have been traversed, so nextp should be itself. If the right children of the predecessor of nextp equal to NULL that means real next pointer should be the smallest of the left side of nextp.

    class BSTIterator {
        private:
            TreeNode* nextp;
    public:
        BSTIterator(TreeNode *root) {
            nextp = root;
        }
        
        void MorrisTraversal(TreeNode* root)
        {
            if(root == NULL)
                nextp = NULL;
            else
            {
                TreeNode* cur = root;
                while(cur->left != NULL)
                {
                     //find the predecessor node of cur node 
                    TreeNode* prenode = cur->left;
                    while(prenode->right != NULL && prenode->right != cur) 
                        prenode = prenode->right;
                    //determine the next node 
                    if(prenode->right == NULL)
                    {
                        prenode->right = cur;
                        cur = cur->left;
                    }
                    else
                    {
                        prenode->right = NULL;
                        nextp = root;
                        return;
                    }
                }
                nextp = cur;
            }
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            if(nextp == NULL)
                return false;
            else
                return true;
        }
    
        /** @return the next smallest number */
        int next() {
            MorrisTraversal(nextp);
            int tmp = nextp->val;
            nextp = nextp->right;
            return tmp;
        }
    };
    

Log in to reply
 

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