Katkat
Back

Find Kth Smallest in BST

UberSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of binary search tree properties, ordered data retrieval, and algorithmic efficiency in locating the k-th smallest element.

You are given the root of a binary search tree and an integer k. Return the value of the node that would appear in the kth position if all node values were listed in ascending order.

A binary search tree has the property that for every node:

  • all values in the left subtree are smaller than the node value, and
  • all values in the right subtree are larger than the node value.

You may assume 1 <= k <= number of nodes in the tree.

Example:

  • Input: root = [5,3,6,2,4,null,null,1], k = 3
  • In-order traversal gives: [1,2,3,4,5,6]
  • Output: 3

Discuss an efficient approach and analyze its time and space complexity.