Given a binary search tree, write a function
kthSmallest to find the kth smallest element in it.
Input: root = [3,1,4,null,2], k = 1
Input: root = [5,3,6,2,4,null,null,1], k = 3
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
- The number of elements of the BST is between
- You may assume
kis always valid,
1 ≤ k ≤ BST's total elements.
Inorder traversal of BST is an array sorted in the ascending order.
we could add a variable to the TreeNode to record the size of the left subtree. When insert or delete a node in the left subtree, we increase or decrease it by 1. So we could know whether the kth smallest element is in the left subtree or in the right subtree by compare the size with k.
# Definition for a binary tree node.