Java Editorial unnecessarily traversing entire tree


#1

The Java editorial solution traverses entire tree even if we had already found k-th smallest in left subtree. We can return immediately as soon as we wind k-th smallest.

public class Solution {
public int kthsmallest(TreeNode A, int B) {
    ArrayList<Integer> path = new ArrayList<>();
    doInOrder(A, B, path);
    return path.get(B-1);
}


private void doInOrder(TreeNode A, int B, ArrayList<Integer> path) {
    
    if(A != null && A.left == null && A.right == null) {
        path.add(A.val);
        return;
        
    }
    if(A.left != null) {
        doInOrder(A.left, B, path);
    }
    if(path.size() >= B) {
        return;    //early return
    }
    path.add(A.val);
    if(path.size() >= B) {
        return;    //early return
    }
    if(A.right != null) {
        doInOrder(A.right, B, path);
    }
    return ;
}

}