Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

126. Kth Smallest Element in a BST

MediumDay 37 of 60Trees & BST

You are given the root of a binary search tree and an integer k. Return the kth smallest value stored in the tree, counting from 1. The tree is a valid BST, so every left subtree holds smaller values and every right subtree holds larger values.

Example 1
Input: root = [3,1,4,null,2], k = 1
Output: 1
Sorted values are 1, 2, 3, 4, so the 1st smallest is 1.
Example 2
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Sorted values are 1, 2, 3, 4, 5, 6 and the 3rd one is 3.
Constraints
  • The number of nodes is n
  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4
Hints
Frequently asked at: Amazon, Meta, Google, Uber
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min