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.

You may assume k is always valid, 1 ? k ? BST's total elements.

Follow up:

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?

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?

**[Thoughts]**

递归遍历二叉树，在遍历过程中算kth。

**[Code]**

```
1: int kthSmallest(TreeNode* root, int k) {
2: int count = 0;
3:
4: return kthSmallestImpl(root, count, k);
5:
6: }
7:
8: int kthSmallestImpl(TreeNode* root, int& count, int k) {
9: if(root == NULL) return -1;
10:
11: int lr = kthSmallestImpl(root->left, count, k);
12: count++;
13: if(count == k) {
14: return root->val;
15: }
16:
17: int rr = kthSmallestImpl(root->right, count, k);
18: return lr != -1 ? lr : rr;
19: }
```

## 3 comments:

Very Nice Post, I learned a lot through it. Thanks for posting.

digitizing for embroidery

Nice post I have learned a lot throughout this blog thanks for sharing keep it up. by cheap digitizing embroidery

The contents of this blog are always very interesting, educative and informative, I must commend you for the good work you are doing here while I urge you to keep it up. Thanks for sharing this wonderful article on digitizing embroidery. Dezinesol is the best graphic design company provided services like logo design , vector art, embroidery digitizing. Place your order today.

Post a Comment