LeetCode - Kth Smallest Element in a BST

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

Example 1:

Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 Output: 3

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 to 10^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 k, stop exploring the rest of nodes.

Code


 /**
 * 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);
	}
}