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.
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?


1:    int kthSmallest(TreeNode* root, int k) {  
2:      int count = 0;  
4:      return kthSmallestImpl(root, count, k);  
6:    }  
8:    int kthSmallestImpl(TreeNode* root, int& count, int k) {  
9:      if(root == NULL) return -1;  
11:      int lr = kthSmallestImpl(root->left, count, k);  
12:      count++;  
13:      if(count == k) {  
14:        return root->val;  
15:      }  
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.