Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) in the tree.
A binary search tree satisfies the following constraints:
- The left subtree of every node contains only nodes with keys less than the node's key.
- The right subtree of every node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees are also binary search trees.
Example 1:
Input: root = [2,1,3], k = 1
Output: 1
Example 2:
Input: root = [4,3,5,2,null], k = 4
Output: 5
Constraints:
1 <= k <= The number of nodes in the tree <= 10,000.0 <= Node.val <= 10,000
Examples
Example 1:
Input: root = [2,1,3], k = 1
Output: 1
Example 2:
Input: root = [4,3,5,2,null], k = 4
Output: 5
Constraints
- `1 <= k <= The number of nodes in the tree <= 10,000`.
- `0 <= Node.val <= 10,000`
Prerequisites
- Binary Tree(Data Structures & Algorithms for Beginners)
- Binary Search Tree(Data Structures & Algorithms for Beginners)
- Depth-First Search(Data Structures & Algorithms for Beginners)
Target: O(N) time • O(1) spaceTree / Depth-First Search / Binary Search Tree / Binary Tree
Socratic AI Tutor
Gemini 3.8 Flash
Loading editor...
Click "Run" or press Ctrl+Enter to execute test cases.