O(k) Java solution
The number of nodes (n) in the tree is irrelevant to the complexity.  My code inorder traverse the tree and it stops when it finds the Kth node.  The time compl
The number of nodes (**n**) in the tree is irrelevant to the complexity.  My code inorder traverse the tree and it stops when it finds the Kth node.  The time complexity for this code is O(k). \n\n=======Update============\n\nThe number of nodes in the tree does change the time complexity. The program actually goes to the left bottom node first and start from there to search for the Kth smallest. Thus the time complexity should be O(log(n) + K). What do you think ?\n\n    public class Solution {\n    public int kthSmallest(TreeNode root, int k) {\n        ArrayList<Integer> buffer = new ArrayList<Integer>();\n        inorderSearch(root, buffer, k);\n        return buffer.get(k-1);\n    }\n    public void inorderSearch(TreeNode node, ArrayList<Integer> buffer, int k){\n        if(buffer.size() >= k)\n            return;\n        if(node.left != null){\n            inorderSearch(node.left, buffer, k);\n        }\n        buffer.add(node.val);\n        if(node.right != null){\n            inorderSearch(node.right, buffer, k);\n        }\n    }\n}
[]