Kth Smallest Element in a BST medium

Problem Statement

Given the root of a binary search tree (BST) and an integer k, return the k^th smallest element in the BST.

You can assume k is always valid, 1 ≤ k ≤ BST's total elements.

Example 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

Steps and Explanation

The most efficient approach to solve this problem leverages the inherent properties of a Binary Search Tree (BST). A BST is ordered: in-order traversal (left, root, right) yields a sorted sequence of nodes. Therefore, we can perform an in-order traversal, keeping track of the elements encountered. The k^th element encountered will be the k^th smallest.

We can implement this using a recursive or iterative approach. The iterative approach often proves slightly more efficient due to avoiding the overhead of recursive function calls. However, for clarity, we'll present a recursive solution.

The recursive function will perform the following:

1. Base Case: If the node is null, we've reached the end of a branch and return.

2. Recursive Step:

   • Recursively traverse the left subtree. This will visit all smaller elements first.
   • Increment count. This tracks the number of nodes visited.
   • If count equals k, we've found the k^th smallest element; return the node's value.
   • Otherwise, recursively traverse the right subtree.

Code (Typescript)

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

function kthSmallest(root: TreeNode | null, k: number): number {
    let count = 0;
    let result: number | null = null;

    function inorderTraversal(node: TreeNode | null): void {
        if (node === null) return;

        inorderTraversal(node.left);
        count++;
        if (count === k) {
            result = node.val;
            return; // Stop traversal once kth element is found
        }
        inorderTraversal(node.right);
    }

    inorderTraversal(root);
    return result!; // result will always be defined because k is guaranteed to be valid
};

Complexity Analysis

• Time Complexity: O(N) in the worst case (skewed tree), where N is the number of nodes in the BST. In a balanced tree, it would be O(k) as we would only traverse a portion of the tree. This is because in the worst case, we might have to traverse the entire tree to find the k^th smallest element.

• Space Complexity: O(H) in the worst case, where H is the height of the BST. This is due to the recursive call stack. In a balanced tree, H would be log(N), while in a skewed tree, H could be N. An iterative approach would reduce space complexity to O(1).

This solution provides a clear and efficient way to find the kth smallest element in a BST using a recursive in-order traversal. Remember that for extremely large trees, an iterative approach could offer a slight performance advantage due to reduced function call overhead.