Find the Kth Smallest Value in a Binary Search Tree

Problem Statement

You are given the breadth-first (level-order) serialization of a binary search tree (BST) as a list of integers and None values, along with a 1-based integer k.

In this serialization:

• The first element is the root.
• Subsequent elements fill nodes level by level from left to right.
• A None indicates an absent child at that position.
• Trailing None values may be omitted.
• All keys in the tree are distinct.

Your task is to reconstruct the BST and return the k-th smallest value in the tree.

Function Signature

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kth_smallest(tree_data: list[int | None], k: int) -> int:
    pass

Examples

Example 1

Input: tree_data = [3, 1, 4, None, 2], k = 1
Output: 1
Explanation:
The tree structure is:
      3
     / \
    1   4
     \
      2
The sorted values are [1, 2, 3, 4]. The 1st smallest value is 1.

Example 2

Input: tree_data = [5, 3, 6, 2, 4, None, 7, 1], k = 3
Output: 3
Explanation:
The tree structure is:
        5
       / \
      3   6
     / \   \
    2   4   7
   /
  1
The sorted values are [1, 2, 3, 4, 5, 6, 7]. The 3rd smallest value is 3.

Constraints

• n (the number of non-null nodes) is between 1 and 10^5.
• 1 <= k <= n
• -10^9 <= Node.val <= 10^9
• All node values are unique.
• The input is guaranteed to represent a valid binary search tree.

Edge Cases to Consider

• k = 1 (minimum element) or k = n (maximum element).
• Left-skewed or right-skewed trees (unbalanced BSTs).
• Trailing nulls omitted from tree_data.