• 42.7%

https://leetcode.com/problems/kth-smallest-element-in-a-bst/#/description

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.

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?

Hint:

1. Try to utilize the property of a BST.
2. What if you could modify the BST node’s structure?
3. The optimal runtime complexity is O(height of BST).

https://discuss.leetcode.com/topic/17573/4-lines-in-c

4 Lines in C++.

Go inorder and decrease k at each node. Stop the whole search as soon as k is zero, and then the k-th element is immediately returned all the way to the recursion top and to the original caller.

Try the left subtree first. If that made k zero, then its answer is the overall answer and we return it right away. Otherwise, decrease k for the current node, and if that made k zero, then we return the current node’s value right away. Otherwise try the right subtree and return whatever comes back from there.

You might notice that I changed k from int to int& because I didn’t feel like adding a helper just for that and the OJ doesn’t mind. Oh well, here is that now:

https://discuss.leetcode.com/topic/18689/share-my-c-iterative-alg

Share my C++ iterative ALG.

https://discuss.leetcode.com/topic/17577/c-solution-using-in-order-traversal

C++ solution using in order traversal

108ms, 27.49%, June.17th, 2016

https://leetcode.com/discuss/44731/pythonic-approach-with-generator

Pythonic approach with generator

With generator in python, one very straightforward solution might be:

https://discuss.leetcode.com/topic/37222/python-easy-iterative-and-recursive-solution

Python Easy Iterative and Recursive Solution

Recursive:

Iterative:

https://discuss.leetcode.com/topic/17583/python-solution-using-iteration

Python Solution using iteration

For the follow up question, I think we could add a variable to the TreeNode to record the size of the left subtree. When insert or delete a node in the left subtree, we increase or decrease it by 1. So we could know whether the kth smallest element is in the left subtree or in the right subtree by compare the size with k.