intermediate8 min read·Updated September 30, 2026

Kth Smallest in a BST Explained: 3rd Smallest in [5,3,6,2,4]

Master the Kth smallest in a BST pattern by walking through the 3rd smallest element in [5,3,6,2,4]. Learn the inorder traversal mental model and edge cases.

By Learnisim AI·Published September 30, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Binary Search Tree properties
  • Tree traversal basics (DFS / Inorder)
  • Recursion and stack fundamentals
Kth Smallest in a BST ($k=3$) — Inorder Traversal Blueprint 1. BST Structure [5, 3, 6, 2, 4] 5 3 6 2 1st (pop) 4 3rd (TARGET) Inorder Sequence (L-R-R) [ 2, 3, 4, 5, 6 ] Index: 1st, 2nd, 3rd, 4th, 5th Halts early at k = 3 (Returns 4) 2. Stack Walk ($k = 3$) Step 1: Push left spine Stack: [5, 3, 2] | node = null Descend left until leaf node. Step 2: Pop 2 (1st smallest) Stack: [5, 3] | count = 1 Check right child of 2 (null). Step 3: Pop 3 (2nd smallest) Stack: [5] | count = 2 Push right child of 3: [5, 4] Step 4: Pop 4 (3rd smallest) Stack: [5] | count = 3 ✓ count == k (3) MATCH! Halt & Return Value: 4 Bypasses nodes 5 and 6 entirely. 3. Why This Wins Time & Space Efficiency Time: O(H + k) average Space: O(H) stack depth No need to store all n nodes! BST Structural Power Left < Root < Right Inorder produces sorted order Without explicit sorting step Immediate Termination Stops exactly at count == k Skips remaining subtrees Optimal for small k in huge trees
3rd smallest in [5,3,6,2,4,null,null] (2,3,4,5,6) overview diagram
Why

Why We Need a Smarter Way to Find the 3rd Smallest in a BST

Phase 1: The BST Traversal Puzzle

Imagine you are handed a Binary Search Tree with nodes [5, 3, 6, 2, 4, null, null]. Visually, this is a root node 5 with a left child 3 (which itself has children 2 and 4) and a right child 6. Your goal is simple: find the 3rd smallest element, where .
If you sort the elements, the sorted order is . Counting up to the 3rd position gives us 4. But how do you make a computer figure this out without writing the entire tree into a flat array first?
If you dump every single node into an array and sort it, you are ignoring the structural gift a Binary Search Tree already gives you. A BST is already semi-ordered: everything in the left subtree is smaller than the root, and everything in the right subtree is larger. Storing all nodes just to find the 3rd smallest wastes memory and discards the structural shortcuts baked into the tree.
We need an approach that explores the tree in sorted order directly, stopping the exact moment we hit our target .
Finding the 3rd Smallest in a BST (k = 3) In-order traversal visits nodes in sorted order: Left -> Root -> Right. Stop when count == k. BST Structure [5, 3, 6, 2, 4] 1 2 1st (k=1) 4 3rd (TARGET!) 3 2nd (k=2) 5 4th 6 5th In-Order Traversal Sequence: [ 2 -> 3 -> 4 (STOP!) -> 5 -> 6 ] Naive: Dump to Array & Sort 1. Visit all nodes 2. Store in Array 3. Sort O(N log N) Wastes Memory & Ignores BST Structure: Discards semi-ordered property; forces full traversal even if k=1. Smart: In-Order Traversal with Early Exit Go Left Subtree Process Node (k--) If k==0: STOP Why This Wins (O(H + k) Time, O(H) Space): • Explores naturally sorted order without extra storage arrays. • Halts computation the exact microsecond the 3rd element is found.
Why We Need a Smarter Way to Find the 3rd Smallest in a BST diagram
Model

Building the Inorder Traversal Mental Model for a BST

Phase 2: The Inorder Blueprint

To find the smallest element in our BST without traversing blind, we rely on a fundamental property of Binary Search Trees: the inorder traversal (Left, Root, Right) always visits nodes in strictly ascending order. For our locked working example where the tree is rooted at 5, with left child 3 (having children 2 and 4) and right child 6, a complete inorder traversal naturally yields the sorted sequence .
Instead of wasting time and memory dumping all elements into a list and indexing at index , we can track our visits on the fly. As we descend down the left spine toward the minimum value, we decrement or increment a counter. When our visit count hits , the current node is our target.
5
/ \
3 6
/ \
2 4
Inorder sequence: [2, 3, 4, 5, 6]
Index mapping: [1st, 2nd, 3rd, 4th, 5th]
This means our algorithm does not need to visit the entire tree. Once we reach the node during our inorder walk, we can immediately halt and return 4, bypassing the need to examine 5 and 6.
Kth Smallest in a BST: Inorder Traversal Blueprint (k = 3) Inorder traversal (Left → Root → Right) visits BST nodes in strictly ascending order BST Structure & Visit Order 5 (4th) 3 (2nd) 6 (5th) 2 (1st) 4 target! (3rd) Walks Left Spine First Halts immediately at 3rd visited node (4) No need to traverse nodes 5 and 6! Inorder Sequence & Counter State Sorted Inorder Sequence (Left, Root, Right): 2 1st (count=1) 3 2nd (count=2) 4 3rd (k=3!) ✓ 5 4th (skipped) 6 5th (skipped) Why On-The-Fly Counting Beats Full Traversal: ❌ Naive Approach (List & Index): Dumps all nodes into list → O(N) time & space complexity. ✓ Optimized Inorder Counter (On-the-fly): Decrement/increment counter per visit → O(H + k) time! Key Algorithm Insight When visit count == k, return node value instantly & halt recursion.
Building the Inorder Traversal Mental Model for a BST diagram
Worked example

Tracing the Inorder Traversal to Find the 3rd Smallest Value

Phase 3: Walking the BST with a Stack

Now that we know an inorder traversal visits BST nodes in strictly ascending order, let us trace it on our locked example: finding the rd smallest element in the tree rooted at 5, with left child 3 (having children 2 and 4) and right child 6.
We will use an explicit stack to simulate the recursive Left-Root-Right traversal without dumping the entire tree into a separate array. We maintain a running counter of how many nodes we have popped from the stack.
Tree Structure:
5
/ \
3 6
/ \
2 4
Target: k = 3
Given / Setup:
- Stack: []
- Current pointer: node = 5
- Visited count: count = 0
Steps:
1. Push left nodes until we hit null: push 5, push 3, push 2.
- Stack: [5, 3, 2]
- node becomes null (left of 2).
2. Pop from stack (node = 2). Increment count to 1. (1st smallest = 2).
- Stack: [5, 3]
- Move to right child of 2 (null), stack remains [5, 3]. No nodes to push.
3. Pop from stack (node = 3). Increment count to 2. (2nd smallest = 3).
- Stack: [5]
•Move to right child of 3, which is 4. Push 4.

- Stack: [5, 4]
4. Pop from stack (node = 4). Increment count to 3. Since count == k, we immediately stop and record our result.
Result:
- The algorithm halts at node = 4 and returns 4, avoiding any unnecessary visits to node 5 or node 6.
Try this: Given k = 3 and stack [5, 4] after popping 3, verify why node 4 is popped next and how count reaches 3.
Tracing Inorder Stack: Finding 3rd Smallest (k = 3) Halts immediately when count == k (Result = 4) BST Node Layout & Halt Point 5 3 6 2 4 Target Reached: node = 4 Popped 3rd! count reaches k = 3 Halt traversal & return 4 Explicit Stack Evolution (Left-Root-Right) Step 1: Push left until null Stack: [5, 3, 2] | node = null Step 2: Pop 2 -> count = 1 (1st smallest) Stack: [5, 3] | right(2) is null Step 3: Pop 3 -> count = 2 (2nd smallest) Push right child (4). Stack: [5, 4] Step 4: Pop 4 -> count = 3 (3rd smallest) count == k (3 == 3). Immediate HALT! Skips visiting node 5 and node 6 entirely
Tracing the Inorder Traversal to Find the 3rd Smallest Value diagram
Practice

Predicting the Traversal State for a Different k

Phase 4: Practice

Now that you have traced the standard pass through our BST where the result is 4, let us test your mental model by changing the target rank. Imagine we run the same iterative inorder traversal on this exact same tree, but we set our target to instead of .
Recall how the stack pushes left children before visiting and incrementing the counter. Without writing a full program, trace through the first few steps of the stack operations and node pops.
Question:
When running the iterative inorder traversal to find the smallest element () in the BST , which node value is popped first, and immediately after that pop, what is the exact state of the stack?
Apply

Transferring the BST Inorder Pattern to a Related Tree Query

Phase 5: Transferring the Inorder Strategy

Now that you have traced the stack state for our BST with , let us test how this same controlled traversal adapts when the tree topology changes. In many production systems, finding the -th smallest element is just a stepping stone to solving range queries or finding the predecessor and successor of a node.
Instead of reconstructing a new traversal strategy from scratch, you can reuse the exact same Left-Root-Right generator logic. The insight from our working example is that early stopping prevents wasted operations—you never need to push or pop nodes once your counter hits .
Consider how you would modify this logic if you needed to find the -th largest element instead of the -th smallest. By simply reversing the traversal order from Left-Root-Right to Right-Root-Left, the stack naturally processes elements in descending order, letting you find the -th largest with identical time complexity.
python
# Conceptual shift: Right-Root-Left for kth largest
def kth_largest(root, k):
    stack = []
    curr = root
    count = 0
    
    while stack or curr:
        while curr:
            stack.append(curr)
            curr = curr.right  # Go right first
        curr = stack.pop()
        count += 1
        if count == k:
            return curr.val
        curr = curr.left   # Then go left
python
def kth_largest(root, k):
    # Using our BST [5, 3, 6, 2, 4, None, None], what is returned if k = 2?
    pass

FAQ

How do we find the 3rd smallest value in the BST [5,3,6,2,4]?
By performing an inorder traversal (Left, Root, Right), visiting nodes in ascending order: 2, 3, 4, 5, 6. The 3rd visited node is 4.
Why is inorder traversal ideal for finding the Kth smallest element in a BST?
The Binary Search Tree property ensures that left subtree nodes are smaller and right subtree nodes are larger than the root. An inorder traversal visits nodes in strictly sorted ascending order naturally.
What is the time complexity of finding the Kth smallest element in a BST?
O(H + k) on average, where H is the height of the tree, because we traverse down to the leftmost node and then visit k nodes sequentially. In the worst case, it can be O(N) for a skewed tree.
What is a common pitfall when implementing this algorithm recursively?
A common mistake is failing to maintain the count and current value globally or via reference across recursive calls, which causes the function to lose track of the progress as it unwinds.

Keep learning