/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int KthSmallest(TreeNode root, int k)
        {
            int count = countNodes(root.left);
            if (k <= count)
            {
                return KthSmallest(root.left, k);
            }
            else if (k > count + 1)
            {
                return KthSmallest(root.right, k - 1 - count); // 1 is counted as current node
            }

            return root.val;
        }

        public int countNodes(TreeNode n)
        {
            if (n == null) return 0;

            return 1 + countNodes(n.left) + countNodes(n.right);
        }
}