0230__kth_smallest_element_in_a_bst.md

Kth Smallest Element in a BST

LeetCode link https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

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

graph TD
    root((3))
    root.left((1))
    root.right((4))
    
    lvl_3__empty((x))
    lvl_3__n2((2))
    
    root --> root.left
    root --> root.right
    
    root.left --> lvl_3__empty
    root.left --> lvl_3__n2

Loading

Input:

root = [3,1,4,null,2]
k = 1

Output: 1

Example 2

graph TD
    root((5))
    root.left((3))
    root.right((6))
    
    %% 3rd level
    lvl_3__n2((2)) %% level 3, node 2
    lvl_3__n4((4))
    
    lvl_4__n1((1))
    
    root --> root.left
    root --> root.right
    
    root.left --> lvl_3__n2
    root.left --> lvl_3__n4
    
    lvl_3__n2 --> lvl_4__n1

Loading

Input:

root = [5,3,6,2,4,null,null,1]
k = 3

Output: 3

Constraints

• The number of nodes in the tree is n.
• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^4

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?