For a given node in a BST, you need to know:
values in left subtrees is always smaller than values in the node.
values in right subtrees is always larger than values in the node.
Therefore, if we use in-order traversal (left->root->right), we can get the sorted ascending node values, and the k-th values would be the answer.
And, we can get the answer as long as we traverse BST with exactly k nodes through in-order traversal.
==> Just utilize variable k to keep track of number of nodes we have traverse. If we find k has subtracted to zero, we just stop traversing the tree and return the value.
Followings are my sample Python code:
def kthSmallest(self, root, k): return self.helper(root, k) def helper(self, node, k): val = node.val #k-th node is somewhere in the left-subtree if node.left: val, k = self.helper(node.left, k) if k == 0: return val, k #k-th node is exactly this node k -= 1 if k == 0: return node.val, k #k-th node is somewhere in the right-subtree if node.right: val, k = self.helper(node.right, k) if k == 0: return val, k #There would be no more than k nodes under this node, need to further traverse return node.val, k
Since integer is immutable in Python, we can not do "pass by reference" just like in C++.
Therefore, I need a dummy function helper to return the updated k.