Kth Smallest Element in a BST

Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed) in the tree. Kth Smallest Element in a BST Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed) in the tree. SWE medium bst tree tree-traversal recursion Frequency Low Last asked 2026-04-13 Stage phone-screen Kth Smallest Element in a BST Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) in the tree. A binary search tree satisfies the following constraints: The left subtree of every node contains only nodes with keys less than the node's key. The right subtree of every node contains only nodes with keys greater than the node's key. Both the left and right subtrees are also binary search trees. Examples Example 1: Input: root = [2,1,3], k = 1 Output: 1 Example 2: Input: root = [4,3,5,2,null], k = 4 Output: 5 Constraints 1 <= k <= The number of nodes in the tree <= 1000 0 <= Node.val <= 1000 Notes The baseline is an in-order traversal (which visits BST nodes in ascending order), stopping after the kth value. The standard recursive or explicit-stack approach uses O(h) space for the tree height. O(1) extra space follow-up A common follow-up asks for a solution with O(1) extra space — no recursion and no explicit stack. Use Morris in-order traversal: for each node, link its in-order predecessor's right pointer to itself to create a temporary thread, walk down to the leftmost node, emit values in ascending order, and unlink each thread once traversed. Count emitted values until the kth is reached. Kth-largest variant The same structure also answers the kth-largest element: run the traversal in reverse in-order (right subtree, node, left subtree), which yields values in descending order, and stop at the kth emitted value.