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

For example: Given binary search tree
     5
   /  \
  3    20
       / \
      17  28
2nd smallest element is 5
3rd smallest element is 20

Since the tree is BST it is known that inorder traversal will return a sorted order of the elements in the tree. While doing an inorder traversal decrement k by 1 and when k reaches 0 the element is found. This approach takes O(logk) which is a reasonable time.

Another way to optimize it further is that while creating a BST, each node can have a counter which can tell how many child nodes are present. This will help to decide whether to move left or right depending on the child nodes and will require lesser iterations.

public class Solution { 
	int number = -1;
	public int kthSmallest(TreeNode root, int k) {
		if (root == null)
			return number;
		inOrder(root, k);
		return number;
	}

	int count= 0;
	private void inOrder(TreeNode root,  int k) {
		if (root.left != null) {
			inOrder(root.left, k);
		}
		count++;
		if (count == k) {
			number = root.val;
			return;
		}
		if (root.right != null) {
			inOrder(root.right, k);
		}
	}
}