## Monday, August 7, 2017

### [Leetcode] Kth Smallest Element in a BST, Solution

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?

[Thoughts]

[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:    }
``````

James David said...

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

JamesF Jones said...

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

James henry said...

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.

Embroidery said...

Hi, I am Mary with more than 11 years of experience in embroidery digitizing. I love to do the job and will provide you high quality services at an affordable price.