Find the kth Smallest Element in a BST - Algorithm and Code Examples

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

Problem Statement❯

Given the root of a Binary Search Tree (BST) and an integer k, return the kth smallest value among all the nodes in the BST. The BST property ensures that the left subtree contains only nodes with values less than the root, and the right subtree only nodes with values greater than the root.

You can assume that 1 ≤ k ≤ N, where N is the number of nodes in the tree.

Examples❯

Input Tree k Output Description
[5, 3, 7, 2, 4, 6, 8]
3 4 In-order traversal gives [2, 3, 4, 5, 6, 7, 8], so 3rd smallest is 4
[10, 5, 15, 3, 7, null, 18]
4 10 In-order: [3, 5, 7, 10, 15, 18]; 4th element is 10
[20, 8, 22, 4, 12, null, null, null, null, 10, 14]
5 14 In-order: [4, 8, 10, 12, 14, 20, 22]; 5th element is 14
[3, 1, 4, null, 2]
1 1 In-order: [1, 2, 3, 4]; 1st element is 1
[2, 1, 3]
2 2 In-order: [1, 2, 3]; 2nd element is 2
[1]
1 1 Single node is the only (and thus 1st) element in-order

Visualization Player

Solution❯

The key idea to solve this problem lies in the structure of a Binary Search Tree (BST). In a BST, if we perform an in-order traversal (i.e., visit left subtree → root → right subtree), we get the elements in ascending sorted order.

Let’s break down the problem based on various scenarios:

1. Normal Case:

If the BST has enough nodes (at least k nodes), we can simply perform an in-order traversal and keep track of how many nodes we’ve seen. When we visit the kth node in this order, that’s our answer. For example, if we need the 3rd smallest element in a tree with values [2, 3, 4, 5, 7, 8], we count as we visit nodes and return the 3rd one: 4.

2. Left-Skewed Tree:

In this case, the smallest values are deeper in the left. Traversing left first guarantees that we visit smaller nodes early. If the tree is just a descending chain, the smallest elements are at the bottom. The logic remains the same — an in-order traversal still works.

3. Right-Skewed Tree:

Similar to the left-skewed case, but here the smallest elements are at the top. Traversal still yields sorted order, so counting until the kth value is still valid.

4. Edge Case – Empty Tree:

If the tree is empty, it has no nodes. Any value of k is invalid here because there’s nothing to choose. We should handle this case gracefully by returning None or raising an exception.

5. k Larger Than Node Count:

This is typically ruled out by problem constraints (i.e., assume 1 ≤ k ≤ N), but in practical implementations, it’s still important to check this scenario to avoid index errors or incorrect results.

In summary, the in-order traversal approach is effective and intuitive because it leverages the natural sorted ordering of BSTs. The only tricky parts involve handling invalid input, such as empty trees or out-of-bound values for k.

Algorithm Steps❯

  1. Given a binary search tree (BST) and an integer k.
  2. Perform an in-order traversal of the BST, which visits nodes in ascending order.
  3. Keep a counter to track the number of nodes visited.
  4. When the counter equals k, record the current node's value as the kth smallest element.
  5. Return the recorded value as the result.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.count = 0
        self.ans = None
        def inorder(node):
            if not node or self.ans is not None:
                return
            inorder(node.left)
            self.count += 1
            if self.count == k:
                self.ans = node.val
                return
            inorder(node.right)
        inorder(root)
        return self.ans

# Example usage:
if __name__ == '__main__':
    # Construct BST:
    #       3
    #      / \
    #     1   4
    #      \
    #       2
    root = TreeNode(3, TreeNode(1, None, TreeNode(2)), TreeNode(4))
    sol = Solution()
    print(sol.kthSmallest(root, 1))