Skip to content
BASA DSA

Kth Smallest Element In a Bst

MediumTrees

Return the kth smallest node value in a strict binary search tree, counting k from one.

Example 1

Argument 1 tree: level-order input; omitted children are null.Argument 1 tree: level-order input; omitted children are null. Vertices: node 0: 5, node 1: 3, node 2: 7, node 3: 2, node 4: 4, node 5: 6, node 6: 8. Edges: node 0 (5) — node 1 (3) left child; node 0 (5) — node 2 (7) right child; node 1 (3) — node 3 (2) left child; node 1 (3) — node 4 (4) right child; node 2 (7) — node 5 (6) left child; node 2 (7) — node 6 (8) right child.5372468
Argument 1 tree: level-order input; omitted children are null.

Input
root = [5,3,7,2,4,6,8]
k = 4
Output
5

Explanation

Inorder is 2,3,4,5,6,7,8, making the fourth value 5.

Example 2

Argument 1 tree: level-order input; omitted children are null.Argument 1 tree: level-order input; omitted children are null. Vertices: node 0: 2, node 1: 1. Edges: node 0 (2) — node 1 (1) left child.21
Argument 1 tree: level-order input; omitted children are null.

Input
root = [2,1]
k = 1
Output
1

Explanation

The left child 1 is the smallest value.

Example 3

Argument 1 tree: level-order input; omitted children are null.Argument 1 tree: level-order input; omitted children are null. Vertices: node 0: 9. Edges: none.9
Argument 1 tree: level-order input; omitted children are null.

Input
root = [9]
k = 1
Output
9

Explanation

The sole node is the first smallest.

Constraints

  • 1 <= k <= number of nodes <= 10000

Function contractkthSmallestArguments: tree, json
Loading draft…
SolutionRuns on your device