Kth Smallest Element in a BST - Medium - L
Published:
Question
- https://leetcode.com/problems/kth-smallest-element-in-a-bst/
Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree.
Approach
- Typical algorithm
Solution
/**
* 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 kthSmallestUtil(TreeNode* root) {
if(root==NULL){
return 0;
}
if(root->left==NULL && root->right==NULL){
return 1;
}
return (1+kthSmallestUtil(root->left)+kthSmallestUtil(root->right));
}
int kthSmallest(TreeNode* root, int k) {
if(root==NULL){
return 0;
}
int x = kthSmallestUtil(root->left);
if(x+1>k){
return kthSmallest(root->left, k);
} else if(x+1==k){
return root->val;
} else{
return kthSmallest(root->right, k-x-1);
}
}
};