kth Smallest Value in a BST

medium bst in-order stack

Problem

Given the root of a BST and a positive integer k, return the kth smallest value.

An in-order walk of a BST yields values in sorted order. Run an iterative in-order traversal with an explicit stack and stop the moment you have popped k nodes — no need to visit the rest.

Inputlevel-order: [5, 3, 6, 2, 4, _, _, 1], k = 3

Output3

In-order: 1, 2, 3, 4, 5, 6 — third value is 3.

level-order ('_' for null) — must be a BST

k (1-based)

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

function kthSmallest(root, k) {
  const stk = []; let cur = root;
  while (stk.length || cur) {
    while (cur) { stk.push(cur); cur = cur.left; }
    cur = stk.pop();
    if (--k === 0) return cur.val;
    cur = cur.right;
  }
}

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

int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> stk;
    TreeNode* cur = root;
    while (!stk.empty() || cur) {
        while (cur) { stk.push(cur); cur = cur->left; }
        cur = stk.top(); stk.pop();
        if (--k == 0) return cur->val;
        cur = cur->right;
    }
    return -1;
}

Time: O(h + k) Space: O(h) stack