Skip to content

content.md

Latest commit

 

History

History
23 lines (14 loc) · 819 Bytes

content.md

File metadata and controls

23 lines (14 loc) · 819 Bytes

Given a binary search tree, write a function kthSmallest to find the k th smallest element in it.

Note:

You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up:

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?

  1. Try to utilize the property of a BST.
  2. What if you could modify the BST node's structure?
  3. The optimal runtime complexity is O(height of BST).

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Show Tags Tree Binary Search

Show Similar Problems (M) Binary Tree Inorder Traversal