#35 · Trees

Kth Smallest Element in a BST

Given the root of a binary search tree and an integer k, return the k-th smallest value (1-indexed) among all node values.

MediumLeetCode

Current node
On the path / call stack
Done / found
Rejected
Temporary thread (Morris)

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Binary search tree + in-order traversal

In-order traversal (left subtree, node, right subtree) of a BST yields the values in ascending order. The k-th smallest value is therefore simply the k-th node visited, so we can stop after k visits.

Memory layout

Pointer-linked nodes; the traversal needs a stack of ancestors (call stack, explicit stack, or threads).

Operation	Cost
in-order traversal of all nodes	O(n)
stop after k nodes	O(h + k)
extra space	O(h), or O(1) with Morris

Stack of ancestors

To visit a node after its left subtree you must remember it while descending. The stack holds exactly the ancestors whose left subtree is currently being explored: at most h entries.

Memory layout

An array (or the call stack) of at most h node references.

Operation	Cost
push / pop	O(1)

Why it fits

The BST ordering makes "sorted order" a free by-product of a traversal: no sorting is needed.
Because the traversal produces values in order, it can stop at the k-th one: for small k the cost is O(h + k), far below O(n).
The iterative version (or Morris) keeps the stopping rule trivial and avoids deep recursion.

Why alternatives degrade

Collect everything and sort:: O(n log n); the BST is already sorted by in-order traversal.
Min-heap of all values:: O(n + k log n) and O(n) memory, ignoring the tree structure.
Full in-order list, then index:: Correct and O(n), but visits and stores every node even when k is tiny.

Four approaches, from naive to production

1 · beginner

Full in-order list, then index

time O(n)space O(n)

Collect all values with an in-order traversal. The list is sorted, so the answer is at index k − 1.

int kthSmallest(TreeNode* root, int k) {
    vector<int> values;
    function<void(TreeNode*)> inorder = [&](TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        values.push_back(node->val);
        inorder(node->right);
    };
    inorder(root);
    return values[k - 1];
}

public int kthSmallest(TreeNode root, int k) {
    List<Integer> values = new ArrayList<>();
    inorder(root, values);
    return values.get(k - 1);
}

private void inorder(TreeNode node, List<Integer> values) {
    if (node == null) return;
    inorder(node.left, values);
    values.add(node.val);
    inorder(node.right, values);
}

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

function kthSmallest(root: TreeNode | null, k: number): number {
  const values: number[] = [];
  const inorder = (node: TreeNode | null): void => {
    if (!node) return;
    inorder(node.left);
    values.push(node.val);
    inorder(node.right);
  };
  inorder(root);
  return values[k - 1];
}

Flaws & bottlenecks

Visits and stores all n nodes even when k = 1.
O(n) extra memory for the list.
Recursion depth equals the tree height.

Interviewer cross-questions

Why is the in-order list sorted?

Say: For every node, all of its left subtree is smaller and all of its right subtree is larger, so visiting left, node, right yields ascending order at every level of the recursion.

Can you avoid visiting everything?

Say: Yes: stop the traversal as soon as the k-th node is visited, using a counter instead of a list.

What if k is out of range?

Say: values[k − 1] would be undefined/out of bounds. Validate 1 ≤ k ≤ n, or return a sentinel or raise an error.

2 · intermediate

Recursive in-order with a counter

time O(h + k)space O(h)

Count nodes as they are visited in order; when the count reaches k record the value, and stop recursing once count ≥ k.

int kthSmallest(TreeNode* root, int k) {
    int count = 0;
    int answer = 0;
    function<void(TreeNode*)> inorder = [&](TreeNode* node) {
        if (!node || count >= k) return;
        inorder(node->left);
        count++;
        if (count == k) answer = node->val;
        inorder(node->right);
    };
    inorder(root);
    return answer;
}

public int kthSmallest(TreeNode root, int k) {
    int[] state = {0, 0};
    inorder(root, k, state);
    return state[1];
}

private void inorder(TreeNode node, int k, int[] state) {
    if (node == null || state[0] >= k) return;
    inorder(node.left, k, state);
    state[0]++;
    if (state[0] == k) state[1] = node.val;
    inorder(node.right, k, state);
}

def kth_smallest(root, k):
    count = 0
    answer = 0
    def inorder(node):
        nonlocal count, answer
        if not node or count >= k: return
        inorder(node.left)
        count += 1
        if count == k: answer = node.val
        inorder(node.right)
    inorder(root)
    return answer

function kthSmallest(root: TreeNode | null, k: number): number {
  let count = 0;
  let answer = 0;
  const inorder = (node: TreeNode | null): void => {
    if (!node || count >= k) return;
    inorder(node.left);
    count++;
    if (count === k) answer = node.val;
    inorder(node.right);
  };
  inorder(root);
  return answer;
}

Flaws & bottlenecks

Uses mutable state captured by the closure (count and answer).
Recursion depth equals the tree height, which can overflow on a deep tree.
The early exit is a guard at the top of each call, so the stack of pending calls still unwinds.

Interviewer cross-questions

Why check count >= k at the top of the function?

Say: Once the answer is found, every call still waiting on the stack would otherwise go on to visit its right subtree. The guard turns those calls into immediate returns.

What is the complexity?

Say: O(h + k): descend h levels to the smallest node, then visit k nodes in order (each edge is crossed at most twice).

How would you handle many queries on a changing BST?

Say: Augment every node with the size of its left subtree. Then each query is O(h): go left if k ≤ leftSize, right if k > leftSize + 1, else it is the current node. Keep the sizes up to date on insert/delete.

3 · advanced

Iterative in-order, stop at k

time O(h + k)space O(h)

In-order traversal with an explicit stack. Pop nodes in ascending order, decrement k each time, and return the node whose pop makes k zero.

int kthSmallest(TreeNode* root, int k) {
    vector<TreeNode*> stack;
    TreeNode* node = root;
    while (node || !stack.empty()) {
        while (node) {
            stack.push_back(node);
            node = node->left;
        }
        node = stack.back(); stack.pop_back();
        k--;
        if (k == 0) return node->val;
        node = node->right;
    }
    return -1;
}

public int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        k--;
        if (k == 0) return node.val;
        node = node.right;
    }
    return -1;
}

def kth_smallest(root, k):
    stack = []
    node = root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0: return node.val
        node = node.right
    return -1

function kthSmallest(root: TreeNode | null, k: number): number {
  const stack: TreeNode[] = [];
  let node = root;
  while (node || stack.length > 0) {
    while (node) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop()!;
    k--;
    if (k === 0) return node.val;
    node = node.right;
  }
  return -1;
}

Flaws & bottlenecks

Stack memory is O(h): O(n) for a chain.
Modifies the parameter k (fine, but it surprises readers).
The nested loop structure is easy to get wrong.

Interviewer cross-questions

Why is this safer than recursion?

Say: The stack is on the heap, so very deep trees cannot overflow the call stack, and the early return is a plain return from the loop.

Why push all the way down the left spine?

Say: The smallest value in a subtree is its leftmost node. Pushing the spine records the ancestors that will be visited after it.

Can you do it without the stack?

Say: Yes: Morris traversal threads the tree temporarily (O(1) space) at the cost of mutating the tree and a longer, subtler loop.

4 · expert

Morris in-order (O(1) space)

time O(n)space O(1)

Traverse in order without a stack: link each left subtree's rightmost node back to its ancestor with a temporary thread, follow it to climb back, and remove it. Record the k-th value but finish the walk so the tree is restored.

int kthSmallest(TreeNode* root, int k) {
    int count = 0;
    int answer = -1;
    TreeNode* cur = root;
    while (cur) {
        if (!cur->left) {
            count++; if (count == k) answer = cur->val;
            cur = cur->right;
        } else {
            TreeNode* pred = cur->left;
            while (pred->right && pred->right != cur) pred = pred->right;
            if (!pred->right) {
                pred->right = cur;
                cur = cur->left;
            } else {
                pred->right = nullptr;
                count++; if (count == k) answer = cur->val;
                cur = cur->right;
            }
        }
    }
    return answer;
}

public int kthSmallest(TreeNode root, int k) {
    int count = 0;
    int answer = -1;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            count++; if (count == k) answer = cur.val;
            cur = cur.right;
        } else {
            TreeNode pred = cur.left;
            while (pred.right != null && pred.right != cur) pred = pred.right;
            if (pred.right == null) {
                pred.right = cur;
                cur = cur.left;
            } else {
                pred.right = null;
                count++; if (count == k) answer = cur.val;
                cur = cur.right;
            }
        }
    }
    return answer;
}

def kth_smallest(root, k):
    count = 0
    answer = -1
    cur = root
    while cur:
        if not cur.left:
            count += 1
            if count == k: answer = cur.val
            cur = cur.right
        else:
            pred = cur.left
            while pred.right and pred.right is not cur: pred = pred.right
            if not pred.right:
                pred.right = cur
                cur = cur.left
            else:
                pred.right = None
                count += 1
                if count == k: answer = cur.val
                cur = cur.right
    return answer

function kthSmallest(root: TreeNode | null, k: number): number {
  let count = 0;
  let answer = -1;
  let cur = root;
  while (cur) {
    if (!cur.left) {
      count++; if (count === k) answer = cur.val;
      cur = cur.right;
    } else {
      let pred = cur.left;
      while (pred.right && pred.right !== cur) pred = pred.right;
      if (!pred.right) {
        pred.right = cur;
        cur = cur.left;
      } else {
        pred.right = null;
        count++; if (count === k) answer = cur.val;
        cur = cur.right;
      }
    }
  }
  return answer;
}

Flaws & bottlenecks

Cannot return early (it would leave threads behind), so it always costs O(n), even for k = 1.
Mutates the tree while running: unsafe with concurrent readers, and an exception would leave it corrupted.
Harder to read and to prove correct than the stack versions.

Interviewer cross-questions

Why not stop as soon as count equals k?

Say: Stopping would leave temporary threads in the tree. You could cleanly stop by first removing the active threads (walk up and unthread), but the simple version just finishes.

When is it the right tool?

Say: When extra memory must be O(1) and the tree is single-threaded and writable. Otherwise the stack version is simpler and exits early.

What invariant does the thread maintain?

Say: While the left subtree of a node is being traversed, the rightmost node of that subtree points back at the node. Following that pointer after the subtree is exhausted is exactly what the recursion's return would do.

Synchronized code walkthrough

Showing: Full in-order list, then index — shares the player above; click any step to jump.

int kthSmallest(TreeNode* root, int k) {
    vector<int> values;
    function<void(TreeNode*)> inorder = [&](TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        values.push_back(node->val);
        inorder(node->right);
    };
    inorder(root);
    return values[k - 1];
}

public int kthSmallest(TreeNode root, int k) {
    List<Integer> values = new ArrayList<>();
    inorder(root, values);
    return values.get(k - 1);
}

private void inorder(TreeNode node, List<Integer> values) {
    if (node == null) return;
    inorder(node.left, values);
    values.add(node.val);
    inorder(node.right, values);
}

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

function kthSmallest(root: TreeNode | null, k: number): number {
  const values: number[] = [];
  const inorder = (node: TreeNode | null): void => {
    if (!node) return;
    inorder(node.left);
    values.push(node.val);
    inorder(node.right);
  };
  inorder(root);
  return values[k - 1];
}

int kthSmallest(TreeNode* root, int k) {
    int count = 0;
    int answer = 0;
    function<void(TreeNode*)> inorder = [&](TreeNode* node) {
        if (!node || count >= k) return;
        inorder(node->left);
        count++;
        if (count == k) answer = node->val;
        inorder(node->right);
    };
    inorder(root);
    return answer;
}

public int kthSmallest(TreeNode root, int k) {
    int[] state = {0, 0};
    inorder(root, k, state);
    return state[1];
}

private void inorder(TreeNode node, int k, int[] state) {
    if (node == null || state[0] >= k) return;
    inorder(node.left, k, state);
    state[0]++;
    if (state[0] == k) state[1] = node.val;
    inorder(node.right, k, state);
}

def kth_smallest(root, k):
    count = 0
    answer = 0
    def inorder(node):
        nonlocal count, answer
        if not node or count >= k: return
        inorder(node.left)
        count += 1
        if count == k: answer = node.val
        inorder(node.right)
    inorder(root)
    return answer

function kthSmallest(root: TreeNode | null, k: number): number {
  let count = 0;
  let answer = 0;
  const inorder = (node: TreeNode | null): void => {
    if (!node || count >= k) return;
    inorder(node.left);
    count++;
    if (count === k) answer = node.val;
    inorder(node.right);
  };
  inorder(root);
  return answer;
}

int kthSmallest(TreeNode* root, int k) {
    vector<TreeNode*> stack;
    TreeNode* node = root;
    while (node || !stack.empty()) {
        while (node) {
            stack.push_back(node);
            node = node->left;
        }
        node = stack.back(); stack.pop_back();
        k--;
        if (k == 0) return node->val;
        node = node->right;
    }
    return -1;
}

public int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        k--;
        if (k == 0) return node.val;
        node = node.right;
    }
    return -1;
}

def kth_smallest(root, k):
    stack = []
    node = root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0: return node.val
        node = node.right
    return -1

function kthSmallest(root: TreeNode | null, k: number): number {
  const stack: TreeNode[] = [];
  let node = root;
  while (node || stack.length > 0) {
    while (node) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop()!;
    k--;
    if (k === 0) return node.val;
    node = node.right;
  }
  return -1;
}

int kthSmallest(TreeNode* root, int k) {
    int count = 0;
    int answer = -1;
    TreeNode* cur = root;
    while (cur) {
        if (!cur->left) {
            count++; if (count == k) answer = cur->val;
            cur = cur->right;
        } else {
            TreeNode* pred = cur->left;
            while (pred->right && pred->right != cur) pred = pred->right;
            if (!pred->right) {
                pred->right = cur;
                cur = cur->left;
            } else {
                pred->right = nullptr;
                count++; if (count == k) answer = cur->val;
                cur = cur->right;
            }
        }
    }
    return answer;
}

public int kthSmallest(TreeNode root, int k) {
    int count = 0;
    int answer = -1;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            count++; if (count == k) answer = cur.val;
            cur = cur.right;
        } else {
            TreeNode pred = cur.left;
            while (pred.right != null && pred.right != cur) pred = pred.right;
            if (pred.right == null) {
                pred.right = cur;
                cur = cur.left;
            } else {
                pred.right = null;
                count++; if (count == k) answer = cur.val;
                cur = cur.right;
            }
        }
    }
    return answer;
}

def kth_smallest(root, k):
    count = 0
    answer = -1
    cur = root
    while cur:
        if not cur.left:
            count += 1
            if count == k: answer = cur.val
            cur = cur.right
        else:
            pred = cur.left
            while pred.right and pred.right is not cur: pred = pred.right
            if not pred.right:
                pred.right = cur
                cur = cur.left
            else:
                pred.right = None
                count += 1
                if count == k: answer = cur.val
                cur = cur.right
    return answer

function kthSmallest(root: TreeNode | null, k: number): number {
  let count = 0;
  let answer = -1;
  let cur = root;
  while (cur) {
    if (!cur.left) {
      count++; if (count === k) answer = cur.val;
      cur = cur.right;
    } else {
      let pred = cur.left;
      while (pred.right && pred.right !== cur) pred = pred.right;
      if (!pred.right) {
        pred.right = cur;
        cur = cur.left;
      } else {
        pred.right = null;
        count++; if (count === k) answer = cur.val;
        cur = cur.right;
      }
    }
  }
  return answer;
}