Kth Smallest Element in a BST

Given the root of a binary search tree and an integer k, return the value of the kth smallest node in the tree. Pattern focus: Inorder Gives Sorted Sequence. An inorder traversal of a BST visits values in ascending order, so the kth visited node is the answer.

Input Format

root = binary tree root, k = 1-indexed order statistic

Output Format

kth smallest value in the BST

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= k <= number of nodes
  • -10^9 <= node values <= 10^9
  • root and k must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

root = [3,1,4,null,2]
k = 1

Output:

1

Explanation:

The smallest value in the BST is 1.

Example 2:

Input:

root = [3,1,4,null,2]
k = 3

Output:

3

Explanation:

Inorder order is [1,2,3,4], so the 3rd value is 3.

Loading...
Kth Smallest Element in a BST