Given a binary search tree, write a function
Example 1:
Example 2:
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?
Constraints:
- The number of elements of the BST is between
1 to10^4 . - You may assume
k is always valid,1 ≤ k ≤ BST’s total elements .
Solution
As we know that, Inorder traversal of BST will give elements in sorted order. Do traverse inorder and maintain count, Once count is qual to the
Code
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int kth = 0; int cnt = 0; public int kthSmallest(TreeNode root, int k) { kthSmallestTe(root, k); return kth; } private void kthSmallestTe(TreeNode node, int k) { if (node == null || kth!=0) return; kthSmallestTe(node.left, k); cnt++; if (cnt == k) kth = node.val; kthSmallestTe(node.right, k); } } |
Complexity Analysis
Time complexity: O(k).Space Complexity: O(1).
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.