Kth Smallest Element in a BST

Leetcode Problem 230: Kth Smallest Element in a BST

Problem Summary

Given the root of a Binary Search Tree and an integer k, return the k-th smallest value among all the node values. k = 1 means the smallest value.

Constraints:

• The tree has between 1 and 10,000 nodes with unique values.
• Node values are integers in the range [0, 10,000].
• k is a valid integer between 1 and the number of nodes.

Techniques

• Tree
• Depth-First Search
• Binary Search Tree
• Binary Tree

Solution

export 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 stack: TreeNode[] = []
    let current = root
    let currentIndex = 1

    while (current || stack.length > 0) {
        while (current) {
            stack.push(current)
            current = current.left
        }

        current = stack.pop()!

        if (currentIndex++ === k) {
            return current.val
        }

        current = current.right
    }

    return -1
}