1
\$\begingroup\$

Here is my implementation: the goal of the algorithm is to find the kth smallest element in a BST.

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        count = 1
        stack = []
        while True:
            if root:
                #keep traversing until we hit leftmost node in tree
                stack.append(root)
                root = root.left
            else:
                curr = stack.pop()
                if count == k:
                    return curr.val
                count+=1
                root = curr.right

I am having a hard time analyzing the complexity. The solution states how it is O(k+h) for both time and space, where h is the height of tree. For example, I do not understand why the space complexity isn't just O(h), assuming h is the height of the entire tree. Once you find the smallest item, its nodes right subtree could contain be of height>=height previously found between the smallest node and the root, so shouldn't the space be O(h*k), where h is the max depth between a subtrees leftmost child(smallest value) and its root?

\$\endgroup\$
  • \$\begingroup\$ The solution states how [complexity] is O(k+h) for both time and space this seems to contradict my implementation [for leetcode 230] : if you are neither author nor maintainer of this code, your question is off-topic here. \$\endgroup\$ – greybeard Oct 15 '19 at 6:52
  • \$\begingroup\$ (I [don't understand why] space complexity isn't just O(h) all of O(h) is O(k+h) for 0≤k. And, please, do not use one and the same symbol with different interpretations in a single context as you do with h.) \$\endgroup\$ – greybeard Oct 15 '19 at 7:03
  • \$\begingroup\$ @greybeard It's possible Leetcode gives the complexity of the optimal solution, but OP didn't reach it? I don't think this question is really off-topic, even though it seems to ask a lot of questions regarding the big O which isn't really within scope. \$\endgroup\$ – IEatBagels Oct 15 '19 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.