Quick Overview

Build a binary search tree from a breadth-first serialization and return its kth smallest value. The prompt defines one-based rank, explicit nulls, implicitly null trailing slots, distinct keys, valid inputs, and a large-tree bound suitable for iterative in-order traversal.

Find the Kth Smallest Value in a Binary Search Tree

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

# Find the Kth Smallest Value in a Binary Search Tree You are given a binary search tree with distinct integer values and an integer `k`. Return the kth smallest value using one-based rank. Implement: ```text kthSmallestInBST(levelOrder, k) -> integer ``` `levelOrder` is a breadth-first serialization using integers and nulls. Starting with the root, each non-null node consumes the next two available entries as its left and right child; null nodes do not consume child entries. If the serialization ends before a node receives both slots, every absent trailing slot is implicitly null. The input describes a valid binary search tree, `k` is valid, and all values are distinct. ## Constraints - `1 <= nodeCount <= 100,000` - `1 <= k <= nodeCount` - `-10^9 <= nodeValue <= 10^9` ## Examples ### Example 1 ```text levelOrder = [3, 1, 4, null, 2] k = 1 output = 1 ``` ### Example 2 ```text levelOrder = [5, 3, 6, 2, 4, null, null, 1] k = 4 output = 4 ```

Overview: Build a binary search tree from a breadth-first serialization and return its kth smallest value. The prompt defines one-based rank, explicit nulls, implicitly null trailing slots, distinct keys, valid inputs, and a large-tree bound suitable for iterative in-order traversal.

Given a binary search tree with distinct integer values and a valid one-based rank k, return its kth smallest value. levelOrder is a breadth-first serialization containing integers and nulls. Starting at the root, each non-null node consumes the next two available entries as its left and right children; null entries consume no child slots. Missing trailing child slots are implicitly null. The input always describes a valid binary search tree.

Constraints

  • 1 <= nodeCount <= 100,000
  • 1 <= k <= nodeCount
  • -10^9 <= nodeValue <= 10^9
  • All node values are distinct.
  • levelOrder follows the stated breadth-first null serialization and describes a valid BST.

Examples

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

Expected Output: 1

Explanation: The first inorder value is 1.

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

Expected Output: 4

Explanation: Inorder traversal is 1, 2, 3, 4, 5, 6.

Hints

  1. Inorder traversal of a binary search tree visits values in ascending order.
  2. Only non-null nodes need to wait in the construction queue for child entries.

Loading coding console...

Show the approach

Approach

Parse the compact breadth-first serialization by keeping a queue of the non-null nodes that still need child slots. Store child indices in arrays. Then perform an iterative inorder traversal. A BST inorder traversal visits values in strictly increasing order, so the kth visited node is exactly the answer. The iterative stack avoids recursion-depth failure on a 100,000-node chain.

Time complexity:
O(n), where n is the number of non-null nodes.
Space complexity:
O(n) for the parsed tree, construction queue, and traversal stack.