public int kthSmallest(TreeNode root, int k) {
List<Integer> list = new ArrayList<>();
midOrderHelper(list,root,k);
return list.get(k1);
}
private void midOrderHelper(List<Integer> list,TreeNode node,int k){
if(list.size() >= k) return;
if(node == null) return;
if(node.left != null) midOrderHelper(list,node.left,k);
list.add(node.val);
if(node.right != null) midOrderHelper(list,node.right,k);
}
my O(k) java solution,it is fast 1ms


It's not really O(k). Imagine your tree consists of only left child nodes. In that case, it would be O(N + K) ~ O(N). This is in simple order traversal. It also takes additional O(N) space, because again assuming all children are left recursion takes space for every level besides your list.
Same thing here without list:
public int kthSmallest(TreeNode root, int k) { Stack<TreeNode> st = new Stack<TreeNode>(); TreeNode curr = root; while(k > 0) { if(curr == null) { TreeNode top = st.pop(); curr = top.right; k; if(k == 0) { curr = top; break; } } else { st.push(curr); curr = curr.left; } } return curr.val; }