Kth Smallest Element in a BST

This question looks like it needs sorting. But there is a hidden shortcut baked into the tree itself. The interviewer wants to see if you know one special fact about a binary search tree. If you know it, the answer falls out almost for free.

🎯 The Problem

You get a binary search tree and a number k. A binary search tree, or BST, is a tree where every node’s left side holds smaller values and its right side holds larger values. Find the kth smallest value, counting from one.

The rules:

• You are given the root of a BST and a number k.
• Return the kth smallest value in the tree.
• Counting starts at one. So k of 1 means the smallest value.
• So k of 3 means the third smallest value.

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

      3
     / \
    1   4
     \
      2

Explanation: In sorted order the values are 1, 2, 3, 4. The 1st smallest is 1.

The sorted order of these values is 1, 2, 3, 4. The first smallest is 1. If k were 3, the answer would be 3.

Here is the BST drawn out. Notice that left children are smaller and right children are larger.

🐢 Approach 1: Collect and Sort (Brute Force)

Grab every value, sort it, then pick the kth one.

The idea:

• Walk the whole tree in any order.
• Collect all values into a list.
• Sort the list from small to large.

How it works:

• Return the value at position k minus one. Lists start at zero.
• The sort puts the kth smallest in the right spot for you.

Why it is weak:

• You sort everything, even when k is small.
• Sorting adds an O(n log n) cost on top of the walk.
• You ignore the BST’s own shape, which already hands you order.

Here is the collect-and-sort code:

def kth_smallest(root, k):
    values = []
    def walk(node):
        if node:
            values.append(node.val); walk(node.left); walk(node.right)
    walk(root)
    values.sort()
    return values[k - 1]

⚡ Approach 2: In-Order Traversal (Best)

The idea in one line: walk the BST in-order and the values come out already sorted, so the kth one you visit is the answer.

The idea:

• In-order traversal visits the left side, then the node, then the right side.
• The left side is smaller. The right side is larger.
• So left then node then right lines values up from small to big.

How it works:

• Walk the tree in-order.
• Count each value as it comes out.
• When the count reaches k, that value is the answer.
• Stop right there. You do not need to finish the walk.

Why it is fast:

• No sorting at all. The tree’s shape does the ordering.
• For a small k you stop early and skip most nodes.

This diagram shows the in-order visit order for our tree, which comes out sorted.

Steps to Solve

1. Start an in-order walk from the root.
2. Always go as far left as you can first.
3. When you visit a node, increase a counter by one.
4. If the counter equals k, this node’s value is the answer. Stop.
5. If not, move to the right child and keep walking in-order.
6. Return the value you found.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

Node* newNode(int val) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->val = val;
    n->left = NULL;
    n->right = NULL;
    return n;
}

int count = 0;
int answer = 0;

void inorder(Node* node, int k) {
    if (node == NULL) return;
    inorder(node->left, k);          // smaller values first
    count++;
    if (count == k) {                // this is the kth value
        answer = node->val;
        return;
    }
    inorder(node->right, k);         // larger values after
}

int kthSmallest(Node* root, int k) {
    count = 0;
    inorder(root, k);
    return answer;
}

int main(void) {
    Node* root = newNode(3);
    root->left = newNode(1);
    root->right = newNode(4);
    root->left->right = newNode(2);

    printf("%d\n", kthSmallest(root, 1));
    return 0;
}

1

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

int count_ = 0;
int answer = 0;

void inorder(Node* node, int k) {
    if (!node) return;
    inorder(node->left, k);          // smaller values first
    count_++;
    if (count_ == k) {               // this is the kth value
        answer = node->val;
        return;
    }
    inorder(node->right, k);         // larger values after
}

int kthSmallest(Node* root, int k) {
    count_ = 0;
    inorder(root, k);
    return answer;
}

int main() {
    Node* root = new Node(3);
    root->left = new Node(1);
    root->right = new Node(4);
    root->left->right = new Node(2);

    cout << kthSmallest(root, 1) << endl;
    return 0;
}

1

public class KthSmallest {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
    }

    static int count = 0;
    static int answer = 0;

    static void inorder(Node node, int k) {
        if (node == null) return;
        inorder(node.left, k);          // smaller values first
        count++;
        if (count == k) {               // this is the kth value
            answer = node.val;
            return;
        }
        inorder(node.right, k);         // larger values after
    }

    public static int kthSmallest(Node root, int k) {
        count = 0;
        inorder(root, k);
        return answer;
    }

    public static void main(String[] args) {
        Node root = new Node(3);
        root.left = new Node(1);
        root.right = new Node(4);
        root.left.right = new Node(2);

        System.out.println(kthSmallest(root, 1));
    }
}

1

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def kth_smallest(root, k):
    state = {"count": 0, "answer": None}

    def inorder(node):
        if node is None or state["answer"] is not None:
            return
        inorder(node.left)              # smaller values first
        state["count"] += 1
        if state["count"] == k:         # this is the kth value
            state["answer"] = node.val
            return
        inorder(node.right)             # larger values after

    inorder(root)
    return state["answer"]


root = Node(3)
root.left = Node(1)
root.right = Node(4)
root.left.right = Node(2)

print(kth_smallest(root, 1))

1

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function kthSmallest(root, k) {
  let count = 0;
  let answer = null;

  function inorder(node) {
    if (node === null || answer !== null) return;
    inorder(node.left);               // smaller values first
    count++;
    if (count === k) {                // this is the kth value
      answer = node.val;
      return;
    }
    inorder(node.right);              // larger values after
  }

  inorder(root);
  return answer;
}

const root = new Node(3);
root.left = new Node(1);
root.right = new Node(4);
root.left.right = new Node(2);

console.log(kthSmallest(root, 1));

1

Let us walk through the Python version line by line.

We keep state = {"count": 0, "answer": None}. The count tracks how many values we have visited so far. The answer starts as None, which means we have not found it yet. We use a dictionary so the inner function can change these values.

The inner inorder(node) starts with if node is None or state["answer"] is not None: return. The first part stops at empty spots. The second part stops the whole walk once we already have an answer. So we never do extra work after we find it.

The line inorder(node.left) goes left first. This is what makes the order sorted. The left side holds smaller values, so we visit them before the node.

After the left side is done, state["count"] += 1 counts the current node. This is the moment a value comes out in sorted order. So we count it here.

Then if state["count"] == k checks if this is the kth value. If yes, we save node.val into the answer and return. We are done.

If it is not the kth yet, inorder(node.right) walks the right side. The right side holds larger values, so we visit them after the node. When the whole walk ends, state["answer"] holds the kth smallest value, which we return.

⏱️ Time and Space Complexity

The brute force visits every node and then sorts, which adds an O(n log n) cost on top. The in-order walk only visits nodes until it reaches the kth one. In the worst case k is large, so it visits all n nodes, giving O(n) time. But for a small k it stops early. For space, the recursion uses the call stack, which goes as deep as the tree. So the space is O(h), where h is the height. The whole win comes from the BST’s order, which hands you a sorted walk for free.

🧩 Key Takeaways

• ✅ A BST keeps smaller values on the left and larger values on the right.
• ✅ An in-order walk visits left, then node, then right, so values come out sorted.
• ✅ Count values as they come out and stop when the count reaches k.
• ✅ You never need to sort, because the tree’s shape does it for you.
• ✅ Stopping early on small k saves you from walking the whole tree.

🚀 What’s Next?

• Validate Binary Search Tree
• Range Sum of BST