Find kth smallest element in BST

题目描述

解题方法

Solution

class Solution:
    # @param root : root node of tree
    # @param k : integer
    # @return an integer
    def kthsmallest(self, root, k):
        if not root:
            return
        stack = []
        curr = root
        i = 0
        while curr or stack and i < k:
            if curr:
                stack.append(curr)
                curr = curr.left
            else:
                node = stack.pop()
                i += 1
                if node.right:
                    curr = node.right

        return node.val

Reference