Kth Smallest Element in a BST

Problem: Kth Smallest Element in a BST

We just use a stack to do in-order search to find our answer.

Code in Python:

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        stack, num = [root], 0
        while stack:
            if stack[-1].left:
                stack.append(stack[-1].left)
                stack[-2].left = None
            else:
                if num == k - 1: return stack[-1].val
                else:
                    num += 1
                    node = stack.pop()
                    if node.right: stack.append(node.right)