Quick Overview

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

Find Kth Smallest in BST

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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 `k`th 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.

Quick Answer: 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 (BST) 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 BST has the property that every value in a node's left subtree is smaller than the node's value, and every value in a node's right subtree is larger than the node's value. For this problem, the tree is provided as a level-order list where None represents a missing child.

Constraints

  • 1 <= number of nodes in the tree <= 10000
  • 1 <= k <= number of nodes in the tree
  • All node values are unique integers
  • -100000 <= node value <= 100000
  • The input tree satisfies the binary search tree property

Examples

Input: ([5, 3, 6, 2, 4, None, None, 1], 3)

Expected Output: 3

Explanation: The in-order traversal is [1, 2, 3, 4, 5, 6], so the 3rd smallest value is 3.

Input: ([10], 1)

Expected Output: 10

Explanation: There is only one node, so the 1st smallest value is 10.

Hints

  1. What traversal of a BST visits values in ascending order?
  2. You do not need to store every value; count nodes as you visit them and stop when you reach k.

Loading coding console...