LeetCode 230 - Kth Smallest Element in a BST

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

This problem gives us the root of a Binary Search Tree, abbreviated as BST, along with an integer k. We need to return the kth smallest value in the tree.

A Binary Search Tree has a very important property:

Every value in the left subtree is smaller than the current node.
Every value in the right subtree is larger than the current node.

Because of this ordering property, if we traverse the tree in a specific order called an inorder traversal, the values appear in sorted ascending order.

The problem is essentially asking:

"If you collected all node values from the BST into a sorted list, what would the kth element be?"

For example, consider this BST:

Its inorder traversal is:

[1, 2, 3, 4]

If k = 1, the answer is 1.

If k = 3, the answer is 3.

The constraints tell us several useful things:

The tree contains at least one node.
k is always valid, meaning 1 <= k <= n.
The maximum number of nodes is 10^4, which is large enough that inefficient repeated sorting approaches are undesirable.
Node values are non-negative integers.

The problem guarantees that the input tree is a valid BST, so we do not need to verify BST correctness ourselves.

Several edge cases are important:

A tree with only one node.
A completely skewed tree that behaves like a linked list.
k = 1, where we want the smallest element.
k = n, where we want the largest element.
Deep recursive traversal in highly unbalanced trees.

These cases can expose issues in traversal order or stopping conditions.

Approaches

Brute Force Approach

The simplest solution is to traverse the entire tree, collect every node value into an array, sort the array, and then return the kth smallest element.

The steps are:

Perform any traversal of the tree.
Store all node values in a list.
Sort the list.
Return values[k - 1].

This works because sorting guarantees ascending order, regardless of how the tree was traversed.

However, this approach ignores the BST property entirely. A BST already contains ordered structure, so sorting again is unnecessary work.

The sorting step costs O(n log n) time, which is slower than necessary.

Optimal Approach

The key observation is that an inorder traversal of a BST naturally visits nodes in ascending sorted order.

The inorder traversal order is:

Visit left subtree
Visit current node
Visit right subtree

Because BST nodes are ordered relative to their subtrees, this traversal produces sorted values automatically.

Instead of storing every value, we can count nodes as we traverse. Once we visit the kth node, we immediately return its value.

This improves efficiency because:

We avoid sorting entirely.
We can terminate early once the answer is found.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Collect all values and sort them
Optimal	O(h + k) average, O(n) worst	O(h)	Inorder traversal with early stopping

Here, h represents the height of the tree.

Algorithm Walkthrough

Optimal Inorder Traversal Algorithm

Initialize a counter to track how many nodes have been visited during inorder traversal.

Since inorder traversal visits nodes in sorted order, the first visited node is the smallest, the second visited node is the second smallest, and so on. 2. Start recursive inorder traversal from the root.

For each node:

Traverse the left subtree first because smaller values exist there.
Process the current node after the left subtree.
Traverse the right subtree last because larger values exist there.

When visiting the current node, increment the counter.

This tells us how many sorted elements we have seen so far. 4. Check whether the counter equals k.

If it does, we have reached the kth smallest element, so store and return its value immediately. 5. Stop traversal early once the answer is found.

There is no need to continue exploring the tree after locating the target node.

Why it works

The correctness comes directly from the BST property.

For every node:

All values in the left subtree are smaller.
All values in the right subtree are larger.

Inorder traversal always visits:

left subtree -> node -> right subtree

Therefore, nodes are visited in strictly ascending order. The kth visited node must be the kth smallest element in the tree.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.count = 0
        self.answer = -1

        def inorder(node: Optional[TreeNode]) -> None:
            if not node or self.answer != -1:
                return

            inorder(node.left)

            self.count += 1

            if self.count == k:
                self.answer = node.val
                return

            inorder(node.right)

        inorder(root)

        return self.answer

The implementation follows the inorder traversal strategy directly.

We maintain two instance variables:

self.count, tracks how many nodes have been visited.
self.answer, stores the final result once found.

The recursive helper function performs inorder traversal.

The base case stops recursion when:

The node is None
The answer has already been found

Traversing the left subtree first guarantees smaller values are processed before the current node.

After returning from the left subtree, we increment the counter because the current node is now being visited in sorted order.

When self.count == k, we have found the kth smallest element and store it in self.answer.

The traversal then exits early to avoid unnecessary work.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func kthSmallest(root *TreeNode, k int) int {
    count := 0
    answer := -1

    var inorder func(node *TreeNode)

    inorder = func(node *TreeNode) {
        if node == nil || answer != -1 {
            return
        }

        inorder(node.Left)

        count++

        if count == k {
            answer = node.Val
            return
        }

        inorder(node.Right)
    }

    inorder(root)

    return answer
}

The Go solution mirrors the Python implementation closely.

Instead of instance variables, Go uses local variables captured by the recursive closure.

Go uses nil instead of Python's None.

The recursive function is declared using a function variable so it can call itself recursively.

Since the problem guarantees a valid answer exists, returning -1 only serves as a placeholder initialization value.

Worked Examples

Example 1

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

Tree:

Inorder traversal order:

1 -> 2 -> 3 -> 4

Traversal process:

Step	Current Node	Count	Answer
1	Visit 1	1	1
2	Stop early	1	1

Since k = 1, the first visited node is the answer.

Final result:

Example 2

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

Tree:

Inorder traversal order:

1 -> 2 -> 3 -> 4 -> 5 -> 6

Detailed traversal:

Step	Current Node	Count	Answer
1	Visit 1	1	-
2	Visit 2	2	-
3	Visit 3	3	3
4	Stop early	3	3

The third visited node is 3, so the result is:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(h + k) average, O(n) worst	We visit nodes in sorted order until reaching the kth element
Space	O(h)	Recursive call stack depth equals tree height

In a balanced BST, the height is O(log n), so recursion depth remains small.

In the worst case, the BST may become completely skewed, making the height O(n).

The traversal may stop early after visiting only k nodes, which is why the average runtime is often better than traversing the entire tree.

Test Cases

# Helper TreeNode class for testing
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, k):
        self.count = 0
        self.answer = -1

        def inorder(node):
            if not node or self.answer != -1:
                return

            inorder(node.left)

            self.count += 1

            if self.count == k:
                self.answer = node.val
                return

            inorder(node.right)

        inorder(root)
        return self.answer

sol = Solution()

# Example 1
root1 = TreeNode(3)
root1.left = TreeNode(1)
root1.right = TreeNode(4)
root1.left.right = TreeNode(2)

assert sol.kthSmallest(root1, 1) == 1  # smallest element

# Example 2
root2 = TreeNode(5)
root2.left = TreeNode(3)
root2.right = TreeNode(6)
root2.left.left = TreeNode(2)
root2.left.right = TreeNode(4)
root2.left.left.left = TreeNode(1)

assert sol.kthSmallest(root2, 3) == 3  # middle element

# Single node tree
root3 = TreeNode(10)

assert sol.kthSmallest(root3, 1) == 10  # only element

# Right skewed tree
root4 = TreeNode(1)
root4.right = TreeNode(2)
root4.right.right = TreeNode(3)
root4.right.right.right = TreeNode(4)

assert sol.kthSmallest(root4, 4) == 4  # largest element

# Left skewed tree
root5 = TreeNode(4)
root5.left = TreeNode(3)
root5.left.left = TreeNode(2)
root5.left.left.left = TreeNode(1)

assert sol.kthSmallest(root5, 2) == 2  # traversal through deep left chain

# Balanced BST
root6 = TreeNode(8)
root6.left = TreeNode(4)
root6.right = TreeNode(12)
root6.left.left = TreeNode(2)
root6.left.right = TreeNode(6)
root6.right.left = TreeNode(10)
root6.right.right = TreeNode(14)

assert sol.kthSmallest(root6, 5) == 8  # root is kth smallest

# k equals n
root7 = TreeNode(2)
root7.left = TreeNode(1)
root7.right = TreeNode(3)

assert sol.kthSmallest(root7, 3) == 3  # largest value

Test	Why
Example 1	Verifies smallest element retrieval
Example 2	Verifies traversal ordering in larger BST
Single node tree	Tests minimum input size
Right skewed tree	Tests unbalanced tree behaving like linked list
Left skewed tree	Tests deep recursive left traversal
Balanced BST	Verifies normal balanced-tree behavior
k equals n	Verifies retrieval of largest element

Edge Cases

A single-node tree is the smallest valid input. This case can expose bugs where traversal assumes left or right children exist. The implementation handles this correctly because the recursive function safely returns when encountering None or nil.

A completely skewed tree behaves like a linked list instead of a balanced BST. Recursive depth becomes large, and traversal order becomes especially important. The algorithm still works because inorder traversal remains valid regardless of tree shape.

When k = n, the algorithm must locate the largest element in the BST. This requires traversing nearly the entire tree. Some incorrect implementations stop too early or mishandle counting logic near the end of traversal. Our implementation increments the counter exactly once per visited node, guaranteeing accurate ordering.

Another subtle edge case occurs when k = 1. In this situation, the answer is simply the leftmost node in the BST. The early stopping optimization is important here because it prevents unnecessary traversal of the remaining tree after finding the smallest value.