Asked at

Kth Smallest Element In A BST

Medium
VerifiedTreeDFSStack~20 min

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

An inorder walk visits BST values in ascending order. A node is { val, left, right } with null children. The input arrives as a single object { root, k }.

Examples

in{ root: {val:3, left:{val:1, right:{val:2}}, right:{val:4}}, k: 1 }
out1

Inorder order is 1, 2, 3, 4; the 1st smallest is 1.

in{ root: {val:2, left:{val:1}, right:{val:3}}, k: 2 }
out2

Inorder order is 1, 2, 3; the 2nd smallest is 2.

Constraints

  • 1 ≤ k ≤ number of nodes ≤ 10⁴
  • 0 ≤ node.val ≤ 10⁴
  • The tree is a valid BST.

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.