[LeetCode] Kth Smallest Element in a BST

230. Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
void postOrder(TreeNode* node, int& k, int& res){
if(!node) return;
postOrder(node->left, k, res);
if(res != -1) return;
if(--k == 0) {res = node->val; return;}
postOrder(node->right, k, res);
}
public:
int kthSmallest(TreeNode* root, int k) {
int res = -1;
postOrder(root, k, res);
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/02/06/PS/LeetCode/kth-smallest-element-in-a-bst/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.