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.
Test Cases
Example 1:
Input: root = [3,1,4,null,2], k = 1
Output: 1
Explanation:
3
/ \
1 4
\
2
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Explanation:
5
/ \
3 6
/ \
2 4
/
1
Solution
/**
* 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 {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode> stack;
while (true) {
while (root != nullptr) {
stack.push(*root);
root = root->left;
}
root = &stack.top();
stack.pop();
if (--k == 0) return root->val;
root = root->right;
}
}
};/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
while(true) {
while(root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (--k == 0) return root.val;
root = root.right;
}
}
}# Definition for a binary tree node.
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
while True:
while root is not None:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if k == 0:
return root.val
root = root.right