Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Follow up:
What if the BST is modified (insert/delete operations) often and you
need to find the kth smallest frequently? How would you optimize the
kthSmallest routine?
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution(object):
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
# left first
node = root
nodes = []
n = 0
while node:
nodes.append(node)
node = node.left
while nodes:
node = nodes.pop() # min val
n += 1
if n == k:
return node.val
node = node.right
while node:
nodes.append(node)
node = node.left
return None