# leetcode 230: kth smallest element in a Binary Search Tree

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?

• 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. – greybeard Oct 15 '19 at 6:52
• (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.) – greybeard Oct 15 '19 at 7:03
• @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. – IEatBagels Oct 15 '19 at 12:51