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?
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void helper(TreeNode *root, int k, int& counter, int& ans) {
if (root == NULL) {
return;
}
helper(root -> left, k, counter, ans);
counter++;
if (counter == k) {
ans = root -> val;
return;
}
helper(root -> right, k, counter, ans);
return;
}
int kthSmallest(TreeNode* root, int k) {
int counter = 0, ans;
helper(root, k, counter, ans);
return ans;
}
};
========= Follow up Leetcode ======
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?
Insert and delete in a BST were discussed last week, the time complexity of these operations is , where is a height of binary tree, and for the balanced tree.
Hence without any optimisation insert/delete + search of kth element has complexity. How to optimise that?
That's a design question, basically we're asked to implement a structure which contains a BST inside and optimises the following operations :
- Insert
- Delete
- Find kth smallest
Seems like a database description, isn't it? Let's use here the same logic as for LRU cache design, and combine an indexing structure (we could keep BST here) with a double linked list.
Such a structure would provide:
- time for the insert and delete.
- for the search of kth smallest.
The overall time complexity for insert/delete + search of kth smallest is instead of .
Complexity Analysis
- Time complexity for insert/delete + search of kth smallest: , where is a tree height. in the average case, in the worst case.
- Space complexity : to keep the linked list.
============== another approach ========
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int cnt = countNodes(root->left);
if (cnt == k - 1)
return root->val;
else if (cnt > k - 1)
return kthSmallest(root->left, k);
else
return kthSmallest(root->right, k - cnt - 1);
}
int countNodes(TreeNode *root) {
if (root == nullptr)
return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
======== Another attempt ====
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int counter = 0;
int ans;
bool ansFound = false;
helper(root, counter, ans, k, ansFound);
return ans;
}
void helper(TreeNode *root, int& counter, int& ans, int k, bool& found) {
if (root == NULL || found) {
return;
}
helper(root -> left, counter, ans, k, found);
counter++;
if (counter == k) {
ans = root -> val;
found = true;
return;
}
helper(root -> right, counter, ans, k, found);
}
};
=========== O(log n + k) is the answer =====
=========== O(log n + k) is the answer =====
Approach 1: Recursion
It's a very straightforward approach with time complexity. The idea is to build an inorder traversal of BST which is an array sorted in the ascending order. Now the answer is the
k - 1
th element of this array.
Complexity Analysis
- Time complexity : to build a traversal.
- Space complexity : to keep an inorder traversal.
Approach 2: Iteration
The above recursion could be converted into iteration, with the help of stack. This way one could speed up the solution because there is no need to build the entire inorder traversal, and one could stop after the kth element.
Complexity Analysis
- Time complexity : , where is a tree height. This complexity is defined by the stack, which contains at least elements, since before starting to pop out one has to go down to a leaf. This results in for the balanced tree and for completely unbalanced tree with all the nodes in the left subtree.
- Space complexity : , the same as for time complexity, in the worst case, and in the average case.
Hi,
ReplyDeleteI am jobless now. Please give me some work if you have.
You can pay me whatever you feel reasonable after completion of the task.
What I can do:
Data entry, processing and conversion (I have typing speed more than 60-word per minute)
SEO: link building using various platforms such as forums, blogs, social media, Q&A websites and more
I know some popular programming languages such as PHP, Python, HTML, CSS, AHK etc. but I am not confident to my programming skills.
I can communicate in English comfortably but I'm not a native speaker.
What I can't do:
I can't do complex calculation.
I can't do graphic design related tasks....
Thanks
Pawan
Email: admin@e07.net