O(1) space solution, none-recursion, none-stack


  • 0
    W

    Morris traversal -- O(n) time and O(1) space, none-recursion, none-stack :

    int kthSmallest(TreeNode* root, int k) {
        int x;
        while (root) {
            if (root->left) {
                /* Find the inorer predecessor of current */
                auto pre = root->left;
                while (pre->right && pre->right != root)
                    pre = pre->right;
                
                /* Make current as right child of its inorder predecessor */
                if (!pre->right) {
                    pre->right = root;
                    root = root->left;
                } else {
                /* Revert the changes made in if part to restore the original tree
                   i.e., fix the right child of predecssor */
                    pre->right = nullptr;
                    if (!--k) x = root->val;
                    root = root->right;
                }
            } else {
                if (!--k) x = root->val;
                root = root-> right;
            }
        }
        return x;
    }

Log in to reply
 

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