Kth Smallest Element in a BST

mediumFREETreesBlind 75

Given the level-order array of a BST and an integer k, return the kth smallest value (1-indexed) in the BST.

Example

Input

3,1,4,null,2
1

Output

Reasoning

The given level-order array 3,1,4,null,2 represents a Binary Search Tree (BST) where the parent node is 3, the left child is 1, the right child is 4, and the right child of the left child is 2.
The BST is traversed in-order to obtain the sorted array: 1, 2, 3, 4.
Since k is 1, we need to find the $1^{st}$ smallest element in the sorted array.
The $1^{st}$ smallest element is 1, which is the final output.

Constraints

1 <= k <= number of nodes <= 10^4
0 <= Node.val <= 10^4

Learn this in

Depth First Search & TreesDSA Study Plan

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The problem involves working with a Binary Search Tree (BST), which is a fundamental data structure in computer science. A BST is a tree where each node has at most two children (i.e., left child and right child) and each node represents a value. The key properties of a BST are:

All values in the left subtree of a node are less than the value in the node.
All values in the right subtree of a node are greater than the value in the node.
For any node, all values in the left subtree and right subtree must also follow the above rules.

Understanding the properties of a BST is crucial to solving this problem. Additionally, the concept of level-order traversal is also important, as the problem provides the level-order array of the BST. Level-order traversal involves visiting all nodes at a given level before moving on to the next level.

The problem requires finding the kth smallest value in the BST, which implies that we need to consider the in-order traversal of the BST. In-order traversal visits the left subtree, the current node, and then the right subtree. This traversal order is essential because it allows us to visit the nodes in ascending order, which is necessary for finding the kth smallest value.

Algorithm/Approach

The general approach to solving this problem involves using the properties of a BST to efficiently find the kth smallest value. Since the problem provides the level-order array, we can use this information to construct the BST or to directly find the kth smallest value. The algorithm pattern that can be applied here is a combination of tree traversal and searching.

Step-by-Step Strategy

To solve this problem, follow these steps:

Understand the given level-order array and how it represents the BST.
Determine how to use the level-order array to find the kth smallest value, either by constructing the BST or by using the array directly.
Consider the properties of a BST and how they can be used to efficiently find the kth smallest value.
Choose an appropriate tree traversal method (e.g., in-order traversal) to visit the nodes in ascending order.
Implement the solution, keeping track of the current node and the number of nodes visited to find the kth smallest value.

Common Pitfalls

When implementing the solution, watch out for the following:

Incorrectly assuming the level-order array is already sorted or can be used directly without considering the BST properties.
Failing to consider the 1-indexed nature of k when finding the kth smallest value.
Not handling edge cases, such as an empty BST or k being larger than the number of nodes in the BST.

Time & Space Complexity

The expected time complexity for this problem is $O(n)$ , where $n$ is the number of nodes in the BST, since we may need to visit all nodes to find the kth smallest value. The space complexity depends on the approach used, but it can be $O(n)$ in the worst case if we need to store the entire BST or level-order array. However, a more efficient solution may have a lower space complexity, such as $O(h)$ , where $h$ is the height of the BST, if we only need to store a portion of the tree.

solution.py

Python 3.13

Test results