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?