230. Kth Smallest Element In a Bst - Explanation

Description

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) in the tree.

A binary search tree satisfies the following constraints:

The left subtree of every node contains only nodes with keys less than the node's key.
The right subtree of every node contains only nodes with keys greater than the node's key.
Both the left and right subtrees are also binary search trees.

Example 1:

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

Output: 1

Example 2:

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

Output: 5

Constraints:

1 <= k <= The number of nodes in the tree <= 1000.
0 <= Node.val <= 1000

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the number of nodes in the given tree.

Hint 1

A naive solution would be to store the node values in an array, sort it, and then return the k-th value from the sorted array. This would be an O(nlogn) solution due to sorting. Can you think of a better way? Maybe you should try one of the traversal technique.

Hint 2

We can use the Depth First Search (DFS) algorithm to traverse the tree. Since the tree is a Binary Search Tree (BST), we can leverage its structure and perform an in-order traversal, where we first visit the left subtree, then the current node, and finally the right subtree. Why? Because we need the k-th smallest integer, and by visiting the left subtree first, we ensure that we encounter smaller nodes before the current node. How can you implement this?

Hint 3

We keep a counter variable cnt to track the position of the current node in the ascending order of values. When cnt == k, we store the current node's value in a global variable and return. This allows us to identify and return the k-th smallest element during the in-order traversal.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

A Binary Search Tree (BST) has a special property:

Left subtree < root < right subtree
But this brute-force method does not use the BST property.

We simply:

Traverse the entire tree and collect all node values.
Sort the collected values.
The k-th smallest element is at index k-1 in the sorted list.

Algorithm

Create an empty list arr.
Perform DFS on the tree:
- For every node, append its value to arr.
Sort arr.
Return arr[k-1].

# 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

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        arr = []

        def dfs(node):
            if not node:
                return

            arr.append(node.val)
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        arr.sort()
        return arr[k - 1]

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

2. Inorder Traversal

Intuition

A Binary Search Tree (BST) has an important property:

Inorder Traversal (Left → Node → Right) always gives values in sorted order.

So instead of collecting all values and sorting them manually, we can:

Do an inorder traversal.
This automatically produces values in ascending order.
The k-th element in this inorder list is the answer.

This makes the solution more efficient and uses the BST’s inherent structure.

Algorithm

Create an empty list arr.
Perform inorder DFS:
- Visit the left subtree.
- Add the current node's value to arr.
- Visit the right subtree.
After traversal, arr will be sorted.
Return arr[k-1].

# 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

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        arr = []

        def dfs(node):
            if not node:
                return

            dfs(node.left)
            arr.append(node.val)
            dfs(node.right)

        dfs(root)
        return arr[k - 1]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Recursive DFS (Optimal)

Intuition

In a BST, the inorder traversal (Left → Node → Right) naturally visits nodes in sorted order.

So instead of storing all values, we can:

Traverse the tree in inorder,
Count nodes as we visit them,
Stop as soon as we visit the k-th smallest node.

This avoids extra space and stops early, making it more optimal.

Algorithm

Keep a counter cnt = k.
Perform an inorder DFS:
- Go left.
- When visiting a node:
  - Decrease cnt.
  - If cnt == 0, record this node's value (this is the k-th smallest).
- Go right.
Return the recorded value.

# 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

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        cnt = k
        res = root.val

        def dfs(node):
            nonlocal cnt, res
            if not node:
                return

            dfs(node.left)
            cnt -= 1
            if cnt == 0:
                res = node.val
                return
            dfs(node.right)

        dfs(root)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Iterative DFS (Optimal)

Intuition

In a BST, an inorder traversal (left -> node -> right) gives nodes in sorted order.
Instead of recursion, we simulate this traversal with a stack:

Push all left nodes (go as deep as possible).
Pop the top node - this is the next smallest value.
Move to its right subtree and repeat.
When we pop the k-th node, that's our answer.

This way, we only visit nodes until we reach the k-th smallest — no need to traverse the whole tree.

Algorithm

Initialize an empty stack and set curr = root.
While either stack is not empty or curr is not null:
- Push all left nodes into the stack (curr = curr.left).
- Pop from the stack - this is the next smallest node.
- Decrement k. If k == 0, return that node's value.
- Move to the right subtree (curr = curr.right).
The popped k-th node is the answer.

# 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

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        curr = root

        while stack or curr:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            k -= 1
            if k == 0:
                return curr.val
            curr = curr.right

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

5. Morris Traversal

Intuition

Inorder traversal of a BST gives values in sorted order, so the k-th visited node is the k-th smallest.
But recursion and stacks use extra space.

Morris Traversal allows us to perform inorder traversal using O(1) extra space, by temporarily creating
a "thread" (a right pointer) from a node's predecessor back to the node.

For each node:

If it has no left child - visit it directly.
If it has a left child - find its inorder predecessor.
- If the predecessor's right pointer is empty - create a temporary link to the current node and move left.
- If the predecessor's right pointer already points to the current node - remove the link, visit the node, and move right.

We decrement k each time we "visit" a node.
The node where k becomes 0 is the k-th smallest.

This works because we simulate the inorder order without extra memory.

Algorithm

Set curr = root.
While curr is not null:
- Case 1: No left child
  - Visit curr (decrement k).
  - If k == 0, return curr.val.
  - Move to curr.right.
- Case 2: Has a left child
  - Find the inorder predecessor (pred = rightmost node in left subtree).
  - If pred.right is null:
    - Create a temporary thread: pred.right = curr.
    - Move curr to its left child.
  - Else (thread already exists):
    - Remove the thread: pred.right = null.
    - Visit curr (decrement k).
    - If k == 0, return curr.val.
    - Move to curr.right.
If traversal ends without finding k nodes, return -1.

# 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

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        curr = root

        while curr:
            if not curr.left:
                k -= 1
                if k == 0:
                    return curr.val
                curr = curr.right
            else:
                pred = curr.left
                while pred.right and pred.right != curr:
                    pred = pred.right

                if not pred.right:
                    pred.right = curr
                    curr = curr.left
                else:
                    pred.right = None
                    k -= 1
                    if k == 0:
                        return curr.val
                    curr = curr.right

        return -1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Using Pre-Order or Post-Order Instead of In-Order

A BST's defining property is that in-order traversal yields sorted values. Using pre-order or post-order traversal does not produce sorted output, so you cannot simply pick the k-th visited node. Always use in-order traversal (left, node, right) to get elements in ascending order.

Off-by-One Errors with k

The k-th smallest element is at index k-1 in a zero-indexed array or corresponds to the k-th decrement of a counter starting at k. Mixing up one-based and zero-based indexing leads to returning the wrong element. Be consistent: if using a counter, return when it reaches zero; if using an array, access index k-1.

Not Stopping Early

When counting nodes during traversal, there is no need to visit the entire tree once the k-th element is found. Failing to return early means wasted computation, especially in large trees where k is small. Use a flag or check the counter after each visit to terminate as soon as possible.