Title: Kth Smallest Element in a BST Source: leetcode.com
Given a binary search tree, write a function kthSmallest to find the kth 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?
- Try to utilize the property of a BST.
- What if you could modify the BST node’s structure?
- The optimal runtime complexity is O(height of BST).
Java solution
|
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
/* https://leetcode.com/problems/kth-smallest-element-in-a-bst/ */ import java.util.List; import java.util.ArrayList; class KthSmallestElementinBST { public static void main(String args[]) { KthSmallestElementinBST solution = new KthSmallestElementinBST(); TreeNode root = solution.new TreeNode(2); root.left = solution.new TreeNode(1); root.right = solution.new TreeNode(3); root.right.right = solution.new TreeNode(5); root.right.right.left = solution.new TreeNode(4); System.out.println(solution.kthSmallest(root, 3)); } public int kthSmallest(TreeNode root, int k) { List<Integer> list = null; if(root==null) return -1; else { list = new ArrayList<Integer>(); helper(root, list, k); } //System.out.println(list); return list.get(k-1); } void helper(TreeNode root, List<Integer> list, int k) { if(root.left!=null) helper(root.left, list, k); if(list.size()==k) return; list.add(root.val); if(root.right!=null) helper(root.right, list, k); } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; } } } |