ammar@web:~$
~/leetcode/medium/kth-smallest-element-in-a-bst
Medium·[2026-03-26]

230. Kth Smallest Element in a BST

[#binary-tree, #dfs]

## description

## 230. 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) of all the values of the nodes in the tree.

Example 1:

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

Example 2:

plain text
1Input: root = [5,3,6,2,4,null,null,1], k = 3 2Output: 3

Constraints:

  • –
    The number of nodes in the tree is n.
    • –
      1 <= k <= n <= 104
      • –
        0 <= Node.val <= 104

        Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

        ## notes

        ### Intuition

        Inorder traversal of a BST provides values in sorted, ascending order.

        ### Implementation

        Define a global variable, count, that will count the values seen in the inorder traversal. Define another global variable for the result.

        Define a recursive function for the inorder traversal:

        • –
          If the node is null, return early
          • –
            Recurse on the left node
            • –
              Increment the count
              • –
                If count == k, update the result and return early
                • –
                  Recurse on the right node

                  Call the recursive function on the root and return the result.

                  ### Edge-cases

                  Important to return early after updating the result to ensure we don't process unnecessary nodes.

                  • –
                    Time: O(h), where h is the height of the BST. At the worst-case, we will only traverse the height of the BST.
                    • –
                      Spec: O(h), where h is the height of the BST. Due to the recursive call stack.

                      ### Complexity

                      ## solution

                      python
                      1from typing import Optional 2from lcutils import TreeNode 3 4# Definition for a binary tree node. 5# class TreeNode: 6# def __init__(self, val=0, left=None, right=None): 7# self.val = val 8# self.left = left 9# self.right = right 10class Solution: 11 def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: 12 count = 0 13 res = root.val if root else 0 14 def dfs(node: Optional[TreeNode]): 15 nonlocal count, res 16 if not node: 17 return 18 19 dfs(node.left) 20 count += 1 21 if count == k: 22 res = node.val 23 return 24 dfs(node.right) 25 26 dfs(root) 27 return res 28 29 30if __name__ == "__main__": 31 # Include one-off tests here or debugging logic that can be run by running this file 32 # e.g. print(solution.two_sum([1, 2, 3, 4], 3)) 33 solution = Solution() 34
                      --EOF--