- Using inorder stack method and a counter for the smallest k element
- Time complexity: O(H+k), where H is a tree height. This complexity is defined by the stack, which contains at least H+k elements, since before starting to pop out one has to go down to a leaf. This results in O(logN+k) for the balanced tree and O(N+k) for completely unbalanced tree with all the nodes in the left subtree.
- Space complexity: O(H) to keep the stack, where H is a tree height. That makes O(N) in the worst case of the skewed tree, and O(logN) in the average case of the balanced tree.
Python
class Solution(object):
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
if k == 0:
return None
tracker = 0
treeStack = []
cur = root
while(cur or treeStack):
while cur:
treeStack.append(cur)
cur = cur.left
cur = treeStack.pop()
tracker += 1
if tracker == k:
return cur.val
cur = cur.right
# or use
"""
k -= 1
if not k:
return root.val
"""