Given a binary search tree, write a functionkthSmallestto find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Starting from the root node, check if it has a left node, if not then the current node should be the smallest value then we can look at the right node. If it has a left node, then we find the inorder predecessor of the current node by looking for the right most node in the left node of the current node. rinse and repeat.

class Solution(object):
    def kthSmallest(self, root, k):
        current = root
        while current:
            if current.left:
                left = current.left
                while left.right and left.right != current:
                    left = left.right
                if left.right == current:
                    left.right = None
                    k -= 1
                    if k == 0:
                        return current.val
                    current = current.right
                else:
                    left.right = current
                    current = current.left
            else:
                k -= 1
                if k == 0:
                    return current.val
                current = current.right   

        return current.val