O(k) space, O(n) time, 10+ short lines, 3 solutions


  • 11

    The solutions I've seen so far use O(n) space, either for the recursion stack or for the self-managed stack. Here's an iterative inorder traversal version that only uses O(k) space by using a "stack" cut off at k elements. I called it stac because of that and had to laugh when I then wrote stac(k) :-)


    Solution 1, Python with deque(maxlen=k)

    Using a deque, setting its maximum length to k.

    def kthSmallest(self, root, k):
        stac = collections.deque(maxlen=k)
        while True:
            while root:
                stac.append(root)
                root = root.left
            root = stac.pop()
            if k == 1:
                return root.val
            k -= 1
            root = root.right
    

    Solution 2, C++ with circular vector

    Using a vector of fixed size k and a stack pointer i into it which will be used modulo k.

    int kthSmallest(TreeNode* root, int k) {
        vector<TreeNode*> stac(k);
        int i = 0, j = k;
        while (true) {
            while (root) {
                stac[i++%k] = root;
                root = root->left;
            }
            root = stac[--i%k];
            if (! --j)
                return root->val;
            root = root->right;
        }
    }
    

    Solution 3, C++ with deque

    I really like the previous version, but the fixed size k isn't always necessary, so here's a version using a deque:

    int kthSmallest(TreeNode* root, int k) {
        deque<TreeNode*> stac;
        while (true) {
            while (root) {
                stac.push_front(root);
                while (stac.size() > k)
                    stac.pop_back();
                root = root->left;
            }
            root = stac.front();
            stac.pop_front();
            if (! --k)
                return root->val;
            root = root->right;
        }
    }
    

    And now I'm waiting for the Morris traversalists to show up...


  • 3
    C

    Here comes the Morris Travel, though I think it is not recommended because the OJ will check the original tree as well.

    int kthSmallest(TreeNode* root, int k) {
        TreeNode *left;
        int ans;
        while (root){
            if (root->left){
                left = root->left;
                while (left->right && left->right != root) left = left->right;
                if (left->right == root){
                    left->right = NULL;
                    if (--k == 0) ans = root->val; //cannot just return, need to recover the tree
                    root = root->right;
                }else{
                    if (k <= 0) root = root->right;
                    else{ // if find the kth, we will not travel new subtree.
                        left->right = root;
                        root = root->left;
                    }
                }
            }else{
                if (--k == 0) ans = root->val;
                root = root->right;
            }
        }
        return ans;
    }

  • 0

    I think it is not recommended because the OJ will check the original tree as well.

    What do you mean? I don't see the problem...


  • 0
    A

    because Morris traversal will connect the the next (successor) as its right node, thus it is in some way 'destroying' the original structure of the tree.


  • 0

    But doesn't it disconnect them again and restore the original tree? I think that's what left->right = NULL; does and there's also the "cannot just return, need to recover the tree" comment.


  • 0
    A

    the connection basically doesn't do "count" thing, it helps connect the next one. Morris traversal prints only at two places:

    // 1
    if (cur->left == NULL)
    {
    printf("%d ", cur->val);
    cur = cur->right;
    }

    // 2
    else
    {
    prev->right = NULL;
    printf("%d ", cur->val);
    cur = cur->right;
    }

    so it may exit (in this case is return the kth node) before it removes the connection


  • 0

    I have no idea what you're trying to say. You're not even talking about the given program.


  • 0
    C

    Hi StefanPochmann, sorry late reply. I mean that if the problem only want the kth number, then we can just return it and ignore the change on tree. However, we will get Runtime Error since the problem requires not only kth number but also the original tree.

    As angelvivienne said, Morris traversal will destroy the tree. It's fine to recover it. I just feel the recovery is some sort of 'extra' operation, which is not as beautiful as your 3 solutions :)


  • 1
    Z

    I'm using morris traversal for this problem and kth closet element in BST and always return a RUNTIME ERROR. Now I know why. Thank you so much!


  • 0
    L

    @StefanPochmann How is the python solution you created not O(k) time? You're at most going through k times, not the entire tree.


  • 0

    @haxet I do have to go through the entire tree if the tree is completely "left-leaning" (only left children, no right children).


  • 0
    L

    @StefanPochmann right but your solution returns when k reaches it's limit. Unless k equals n, on average you're going through the tree k times


  • 0

    @haxet Maybe on average, yes. But then it's O(k) average, not O(k).

    How did you determine the average?


  • 0
    L
    This post is deleted!

  • 0

    @haxet said in O(k) space, O(n) time, 10+ short lines, 3 solutions:

    @StefanPochmann Well I was always under the assumption when a run time is given we're looking at the average.

    No, when it's not specified then it's understood as overall, i.e., worst case. (Except for a few rare things where everybody knows that average is meant and where average makes more sense.)

    We don't say sorting is o(n^2), we say it's the average case: o(nlogn)

    It's not o(nlogn). You mean O(nlogn). Little-o does exist and differs from big-O. And check out for example Wikipedia's quicksort article and you'll see that every "O(n log n)" for regular quicksort is appropriately accompanied with the word "average" (or similar).

    same with binary search :on average it's o(logn) not o(n) like the worst case scenario you just described.

    Binary search is O(log n). Not just average O(log n). So I'm not sure what your point is with this.

    I think a more appropriate runtime would be O(min(k,n)) which is always O(k)

    But that's not true.


  • 0
    L

    @StefanPochmann When has anyone referred to an algorithm as anything other than average case? Maybe you should have specified O(n) worst-case?


  • 0

    @haxet said in O(k) space, O(n) time, 10+ short lines, 3 solutions:

    @StefanPochmann When has anyone referred to an algorithm as anything other than average case?

    Pretty much everybody pretty much always?

    I guess you might've gotten the wrong idea because often average and worst case complexity are the same. But like Wikipedia says:

    one commonly uses the worst-case time complexity of an algorithm [...]. Less common, and usually specified explicitly, is the measure of average-case complexity.

    @haxet said in O(k) space, O(n) time, 10+ short lines, 3 solutions:

    Maybe you should have specified O(n) worst-case?

    That's what I did.


  • 0
    L

    @StefanPochmann Well worst case and average case would still be O(k). At worse case, k=n, so technically O(k) still is right?


  • 0

    @haxet No, it's not O(k). Like I said, if the tree is completely "left-leaning" then I do have to go through the entire tree. Regardless of what k is! Even if k is 1!


  • 0
    L

    @StefanPochmann

    I'm just curious what do you think is the time complexity of this:
    class Solution:
    # @param {TreeNode} root
    # @param {integer} k
    # @return {integer}

    def kthSmallest(self, root, k):
    s, cur, rank = [], root, 0

        while s or cur:
            if cur:
                s.append(cur)
                cur = cur.left
            else:
                cur = s.pop()
                rank += 1
                if rank == k:
                    return cur.val
                cur = cur.right
    
        return float("-inf")

Log in to reply
 

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