LeetCode 230: Kth Smallest Element in a BST with Iterative Inorder Traversal

Disclaimer

This article is an independent educational explanation of a programming problem originally published on LeetCode. The original problem statement, examples, constraints, trademarks, and related materials belong to LeetCode and their respective rights holders.

The real-world scenario is a hypothetical educational adaptation and does not represent a confirmed company process unless explicitly stated with a reliable source.

The solution, explanation, and code are for learning and reference. Other valid approaches may exist. Readers should verify current requirements on the original LeetCode page.

Article Summary

In LeetCode 230: Kth Smallest Element in a BST, we are given a Binary Search Tree and an integer k. Our goal is to return the k-th smallest node value.

The most important observation is not about k itself. It is about the special ordering property of a Binary Search Tree (BST).

For every node in a BST:

• Values in the left subtree come before the current node in sorted order.
• The current node comes next.
• Values in the right subtree come after the current node.

That is exactly the same order used by an inorder traversal:

Left -> Node -> Right

Therefore, when we perform inorder traversal on a BST, we visit the node values in sorted ascending order.

Instead of creating an entire sorted array, we can use a stack to perform the traversal and stop as soon as we visit the k-th node.

This problem is an excellent example of how knowing the property of a data structure can eliminate unnecessary work.

---

Original Problem and Credit

This article is based on the LeetCode problem “230. Kth Smallest Element in a BST.”

• Original problem: LeetCode 230 - Kth Smallest Element in a BST
• Platform: LeetCode
• Original problem, examples, and constraints credit: LeetCode
• Explanation, adaptation, analysis, and commentary: Andy

The problem gives us:

• The root of a Binary Search Tree
• An integer k

We need to return the value that would appear in position k if all node values were arranged from smallest to largest.

The important constraints include:

1 <= k <= n <= 10^4
0 <= Node.val <= 10^4

where n is the number of nodes in the tree.

Because k is guaranteed to be between 1 and n, the requested element always exists.

---

Real-World Scenario

Imagine a hypothetical monitoring platform that stores numeric service-response thresholds inside an in-memory Binary Search Tree.

Each node contains one threshold value:

        5
       / \
      3   6
     / \
    2   4
   /
  1

Because the values are stored as a BST, smaller threshold values are found toward the left side of the tree, while larger values are found toward the right side.

Suppose an analyst asks:

What is the third-lowest threshold currently stored in the index?

One possible approach would be:

1. Extract every threshold.
2. Put them into an array.
3. Sort the array.
4. Return the third element.

But the BST is already maintaining useful ordering information.

If we traverse the tree using:

Left -> Node -> Right

we obtain:

1, 2, 3, 4, 5, 6

The third value is therefore:

3

There is no need to sort the values again.

This monitoring platform is hypothetical. It is only used to demonstrate the same computational problem in a realistic engineering context.

---

Examples

Example 1

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

Output:
1

The BST can be visualized as:

      3
     / \
    1   4
     \
      2

Performing inorder traversal:

Left -> Node -> Right

produces:

1, 2, 3, 4

The first smallest value is:

1

Therefore:

Output = 1

---

Example 2

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

Output:
3

The tree looks like:

        5
       / \
      3   6
     / \
    2   4
   /
  1

Its inorder traversal is:

1, 2, 3, 4, 5, 6

The third smallest value is:

3

Therefore:

Output = 3

---

Mapping to the Original Problem

The hypothetical ranking system maps directly to the LeetCode problem.

The scenario does not change the mathematical problem.

We still have:

Binary Search Tree + k

and need to return:

k-th smallest node value

---

Solution Intuition

The key to deriving the solution is recognizing that this is not really a sorting problem.

The tree is already a Binary Search Tree.

Step 1: Remember the BST ordering rule

For a node:

        X
       / \
   smaller larger

all values that should appear before X in sorted order are found in its left subtree.

Values that should appear after X are found in its right subtree.

That means the natural sorted traversal is:

left subtree
current node
right subtree

This is exactly inorder traversal.

---

Step 2: Connect inorder traversal to k

Suppose inorder traversal produces:

1, 2, 3, 4, 5, 6

If:

k = 3

we do not actually care about values:

4, 5, 6

Once we reach:

3

the answer is already known.

So instead of generating the entire inorder traversal, we can count nodes as they are visited:

Visit 1 -> k becomes 2
Visit 2 -> k becomes 1
Visit 3 -> k becomes 0

When:

k == 0

the current node is the answer.

This gives us an important optimization:

Stop the traversal immediately after visiting the k-th node.

---

Why Use a Stack?

We could implement inorder traversal recursively.

However, an iterative solution with a stack makes the traversal process especially clear.

A stack follows the Last-In, First-Out principle:

LIFO = Last In, First Out

The most recently pushed node is the first one removed.

For inorder traversal, we repeatedly move as far left as possible:

current
   |
   v
   5
  /
 3
/
2
/
1

But after reaching 1, we still need to remember that we must eventually return to:

2
3
5

The stack stores this path for us.

For example:

push 5
push 3
push 2
push 1

The stack conceptually contains:

top
 |
 v
1
2
3
5

Now we can visit 1.

After processing it, we pop back to 2, then later 3, and so on.

The stack therefore replaces the call stack that recursive traversal would normally use.

---

Recognizing the Pattern

When a problem gives you a BST and asks about:

• Smallest element
• Largest element
• k-th smallest element
• k-th largest element
• Sorted ordering of nodes
• Rank of a node

you should immediately think about the BST ordering property.

For k-th smallest:

Inorder:
Left -> Node -> Right

For problems involving the largest values, the reverse direction may become useful:

Right -> Node -> Left

The important idea is not to memorize one solution.

Instead, remember:

A BST contains ordering information, and traversal order lets us exploit that information.

---

Algorithm

We maintain:

stack<TreeNode*> st;

and a pointer:

TreeNode* current = root;

Then:

1. Start from root.
2. Move left as far as possible.
3. Push every node encountered onto the stack.
4. When there is no more left child, pop the top node.
5. This popped node is the next node in sorted order.
6. Decrease k.
7. If k == 0, return the current node's value.
8. Otherwise, move to the current node's right subtree.
9. Repeat until the answer is found.

In pseudocode:

current = root

while current exists OR stack is not empty:

    while current exists:
        push current
        current = current.left

    current = stack.top
    stack.pop

    k--

    if k == 0:
        return current.value

    current = current.right

---

Why the Algorithm Works

The correctness comes from one central invariant:

Every node popped from the stack is the next unvisited node in the BST's inorder traversal.

Consider what happens before a node is processed.

We first repeatedly travel left:

while (current != nullptr) {
    st.push(current);
    current = current->left;
}

This guarantees that we reach the smallest currently reachable unvisited node before processing its ancestors.

Once no further left node exists, we pop:

current = st.top();
st.pop();

That node is now the next value in inorder traversal.

After processing it, we move into its right subtree:

current = current->right;

Before processing anything in that right subtree, the algorithm again travels as far left as possible.

Therefore the traversal order is always:

Left -> Node -> Right

For a BST, this produces values in sorted ascending order.

So if the popped nodes are:

v1, v2, v3, ..., vk

then:

v1 = smallest
v2 = second smallest
v3 = third smallest
...
vk = k-th smallest

Every time we pop a node, we decrement:

--k;

Therefore, when:

k == 0

the current node must be exactly the original k-th smallest element.

---

Complexity Analysis

Let:

n = number of nodes in the BST
h = height of the BST

Time Complexity

The iterative traversal does not necessarily need to visit every node.

We stop immediately after finding the k-th smallest value.

Before processing the first value, we may need to descend through a path of height h.

After that, we continue inorder traversal until k nodes have been processed.

A useful way to express this is:

O(h + k)

In the worst case:

k = n

or the tree may be highly skewed.

Therefore the general worst-case time complexity is:

O(n)

Each node that we actually explore is pushed onto the stack at most once and popped at most once.

Stack operations such as:

push()
pop()
top()

take constant time.

So there is no additional sorting cost such as:

O(n log n)

The BST's ordering property allows us to avoid sorting entirely.

---

Space Complexity

The stack stores nodes along the traversal path.

The maximum number of nodes simultaneously stored is related to the height of the tree.

Therefore:

O(h)

auxiliary space is required.

For a relatively balanced tree:

h = O(log n)

so the stack may use:

O(log n)

space.

For a completely skewed tree:

h = O(n)

so the worst-case auxiliary space becomes:

O(n)

Therefore:

Space Complexity: O(h)
Worst case: O(n)

---

Solution: Iterative Inorder Traversal with a Stack

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right)
 *         : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> st;
        TreeNode* current = root;

        while (current != nullptr || !st.empty()) {

            // Move as far left as possible.
            while (current != nullptr) {
                st.push(current);
                current = current->left;
            }

            // The top node is the next value
            // in inorder (sorted) order.
            current = st.top();
            st.pop();

            --k;

            if (k == 0) {
                return current->val;
            }

            // After visiting the current node,
            // process its right subtree.
            current = current->right;
        }

        // LeetCode guarantees 1 <= k <= number of nodes,
        // so execution should never reach this point.
        return -1;
    }
};

---

Walkthrough

Consider:

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

The tree is:

        5
       / \
      3   6
     / \
    2   4
   /
  1

We want the third smallest value.

Initial State

current = 5
k = 3
stack = []

---

Move Left from 5

Push 5:

stack = [5]

Move to:

current = 3

Push 3:

stack = [5, 3]

Move to:

current = 2

Push 2:

stack = [5, 3, 2]

Move to:

current = 1

Push 1:

stack = [5, 3, 2, 1]

Now:

current = nullptr

We cannot move left anymore.

---

Visit Node 1

Pop:

1

Now:

stack = [5, 3, 2]

Decrease k:

k = 2

Since:

k != 0

we continue.

Node 1 has no right subtree:

current = nullptr

---

Visit Node 2

Because current is null, pop the next node:

2

Now:

stack = [5, 3]

Decrease:

k = 1

Again:

k != 0

Node 2 has no right subtree.

---

Visit Node 3

Pop:

3

Now:

stack = [5]

Decrease:

k = 0

We have now visited three nodes in inorder order:

1
2
3

Since:

k == 0

return:

3

Notice that we never needed to visit:

4
5
6

The traversal terminates immediately after finding the requested value.

---

Why Not Store the Entire Inorder Traversal?

Another valid solution would be:

1. Traverse the complete BST.
2. Store every value in a vector.
3. Return values[k - 1].

For example:

vector<int> values;

could eventually contain:

[1, 2, 3, 4, 5, 6]

Then:

values[k - 1]

would give the answer.

This works, but it stores information that we do not actually need.

If:

k = 1

we only need the first value.

Building an entire array of n values would still require:

O(n)

time and:

O(n)

additional storage for the result array.

The stack-based solution instead allows us to stop when the answer has been found.

This is a useful general optimization pattern:

If a traversal produces results in the required order, determine whether you can stop as soon as the requested result appears.

---

Follow-Up: What If We Perform This Query Frequently?

The original problem also raises an interesting follow-up.

Suppose the BST changes frequently through operations such as:

insert
delete

and we also need to answer many k-th-smallest queries.

Running inorder traversal for every query could become expensive.

One possible optimization is to augment each node with the size of its subtree.

Conceptually:

TreeNode
├── value
├── left
├── right
└── subtreeSize

Suppose a node has:

left subtree size = L

Then its rank relative to its subtree is:

L + 1

because all L nodes in its left subtree come before it.

At every node:

if k == L + 1
    current node is the answer

if k <= L
    search left subtree

if k > L + 1
    search right subtree
    k = k - (L + 1)

This allows us to eliminate entire subtrees without traversing them.

If subtree sizes are maintained correctly, a rank query can run in:

O(h)

where h is the height of the tree.

For a balanced BST:

O(log n)

is possible.

For a highly skewed tree:

O(n)

is still possible.

The tradeoff is that insertions and deletions now also need to maintain the subtree-size metadata.

This is closely related to a data structure known as an order-statistic tree.

---

Common Mistakes

1. Using Preorder Instead of Inorder

Preorder uses:

Node -> Left -> Right

This does not produce BST values in sorted order.

For this problem we need:

Left -> Node -> Right

---

2. Thinking the Tree Representation Is Sorted

An input such as:

[5,3,6,2,4,null,null,1]

is a tree representation.

It does not mean:

5, 3, 6, 2, 4, 1

is the order in which values should be ranked.

The ranking comes from BST inorder traversal.

---

3. Moving Right Too Early

For every node, the entire relevant left path must be handled before the node itself.

That is why we first execute:

while (current != nullptr) {
    st.push(current);
    current = current->left;
}

before popping anything.

---

4. Forgetting That k Is 1-Indexed

If:

k = 1

we need the smallest element.

That makes decrementing k after visiting each node particularly convenient:

--k;

if (k == 0) {
    return current->val;
}

---

5. Counting a Node When It Is Pushed

Pushing a node onto the stack does not mean we have visited it in inorder traversal.

For example:

        5
       /
      3
     /
    2

we may push:

5
3
2

but 5 is definitely not the smallest value.

A node becomes part of the inorder result when it is popped and processed.

Therefore k should decrease here:

current = st.top();
st.pop();

--k;

not when the node is pushed.

---

6. Sorting All Values Again

A solution that collects every value and performs:

sort(...)

can work logically, but it ignores the most useful property of the input.

Sorting would introduce:

O(n log n)

time.

Inorder traversal already gives us the required ordering without another sorting operation.

---

Key Takeaways

1. Inorder traversal of a Binary Search Tree produces values in sorted ascending order.

2. When a BST problem asks for a ranked element such as the k-th smallest value, think about traversal order before considering explicit sorting.

3. An iterative inorder traversal uses a LIFO stack to remember ancestors while moving down the left side of the tree.

4. We can stop after visiting the k-th node, so we do not necessarily need to traverse the entire BST.

5. The iterative solution uses O(h) auxiliary space, where h is the tree height, and has O(n) worst-case time complexity.

6. For repeated rank queries on a frequently modified BST, storing subtree sizes can support more efficient order-statistic operations.

The broader lesson is that choosing an algorithm should begin with understanding the guarantees already provided by the data structure. A Binary Search Tree has ordering built into its structure, and inorder traversal is the mechanism that exposes that ordering.