Convert sorted array to binary search tree with mi

I want to convert a sorted integer array into a binary search tree. I have posted my code below. What I cannot picture is how the recursion actually works with the for loop as inserting.

So if my array is [1,3,4, 5,8,10] I make 4, which is the mid of the array, become the root of my BST, then loop from the start of array and insert to the tree with root just created. My question is why the order of result inserted is not as the sorted given array?

public TreeNode sortedArrayToBST(int[] A) {  
    if (A == null || A.length == 0){
       return null;
    }
    TreeNode root = new TreeNode(findMid(A));
    for (int i = 0; i < A.length; ++i){
        insert(root, A[i]);
    }      
 return root;
}




private int findMid(int[] A){

    int left = 0;
    int right = A.length -1;
    int mid = A[left + (right - left)/2];
    return mid;
}

private void insert (TreeNode root, int val){

    if (root == null || root.val == val){
        return;
    }
    if (val < root.val){
            TreeNode left = new TreeNode(val);
            root.left = left;
        }
    if (val > root.val){
            TreeNode right = new TreeNode(val);
            root.right = right;
        }

    insert(root.left,val);
    insert(root.right,val);

}

You have a couple problems with your recursive insert method. First off, everytime the val is not equal to the root's value, you create a new node. This is faulty because by doing this, you create multiple nodes and set the root's child at each step of the recursion to these new nodes, which is redundant. Let's go through your method for each node.

Adding 4

Adding 1

   4
  / 
 1

Adding 3

   4
  /
 3

At this point, we can pinpoint the error. Why was 4's left child replaced with 3? Let's go through your insert method where root is the node with value 4 and val is 3.

First if-statement condition evaluates to false, so move on
Second if-statement condition evaluates to true, so create a new node with val and set root.left equal to this new node
Third if-statement condition evaluates to false, so move on
Recursive call insert(3.left, 3) just returns since 3 == 3
Recursive call insert(null, 3) just returns since root == null

So what's the fix? STOP creating new nodes at every recursive call in the call stack. Believe it or not, you should only be creating a new node when root is null, because this signifies that you've traversed the tree down to an empty child. What about the recursive calls? There's no need to do a recursive call on each of the root's children because you only go down one traversal path in a BST. You either turn left or right at each node. So what you do is only make a recursive call depending on the value of val relative to the root's value. Here's what it should look like,

private TreeNode insert (TreeNode root, int val){

    if (root == null){
        return new TreeNode(val);
    }
    if (val == root.val){
        //if you don't want to add repeats in the tree, then
        //add your own code to deal with that here
        //although as it stands now, this code will not add repeats
    }
    if (val < root.val){
            root.left = insert(root.left, val);
    }
    if (val > root.val){
            root.right = insert(root.right, val);
    }
    return root;
}