insert(I, [], [I, [], [] ] ). how to insert into a binary tree?

Besides the typo (mix3(R, G, N2, G, N)) in your program there is a mistake with the depth: you want to insert the new element in the smaller sub tree. Therefore you need to calculate the depth of a subtree from the minimum of the depth of both subtrees.

Also which prolog are you using? min/3 does not seem to be an inbuild predicate in SWI prolog, so I'm using min/2 instead.

Here is my solution. I do not use the mix predicates.

insert(I, [], [I, [], [] ]):- !.
insert(I, [R, G, D], N):-
    depth(G, P1), 
    depth(D, P2), 
    (   P1=<P2
    ->  insert(I, G, NN),
        N = [R, NN, D]
    ;   insert(I, D, NN),
        N = [R, G, NN]
    ).

depth([], 0).
depth([_, Y, Z], H):-
    depth(Y, H1), 
    depth(Z, H2), 
    H is 1+min(H1, H2).

The cut (!) is not necessary. These are the test cases (ouput tree of one query is the input tree for the next one):

?- insert(1, [], N).
N = [1, [], []].

?- insert(21, [1, [], []], N).
N = [1, [21, [], []], []].

?- insert(22, [1, [21, [], []], []], N).
N = [1, [21, [], []], [22, [], []]].

?- insert(31, [1, [21, [], []], [22, [], []]], N).
N = [1, [21, [31, [], []], []], [22, [], []]].

?- insert(32, [1, [21, [31, [], []], []], [22, [], []]], N).
N = [1, [21, [31, [], []], [32, [], []]], [22, [], []]].

?- insert(33, [1, [21, [31, [], []], [32, [], []]], [22, [], []]], N).
N = [1, [21, [31, [], []], [32, [], []]], [22, [33, [], []], []]].

?- insert(34, [1, [21, [31, [], []], [32, [], []]], [22, [33, [], []], []]], N).
N = [1, [21, [31, [], []], [32, [], []]], [22, [33, [], []], [34, [], []]]]

?- insert(41, [1, [21, [31, [], []], [32, [], []]], [22, [33, [], []], [34, [], []]]], N).
N = [1, [21, [31, [41, [], []], []], [32, [], []]], [22, [33, [], []], [34, [], []]]].

Seems to work.

The main problems with your code are:

• It does not build the new tree resulting from the insertion.
• It does not guarantee that the leaves in the last level of the tree are grouped on the left.

To solve the first problem, you can modify your code as following:

insert(Item, [], [Item,[],[]]).
insert(Item, [Root, Left, Right], NewTree):-
   depth(Left, Dl),
   depth(Right, Dr),
   (   Dl =< Dr
   ->  insert(Item, Left, NewLeft),
       NewTree = [Root, NewLeft, Right]
   ;   insert(Item, Right, NewRight),
       NewTree = [Root, Left, NewRight] ).

depth([], 0).
depth([_, Left, Right], Depth):-
    depth(Left, Dl),
    depth(Right, Dr),
    Depth is 1 + max(Dl, Dr).

show(Tree) :-
    show(Tree, 0).

show([], _) :- !.
show([Root, Left, Right], Depth) :-
    NewDepth is Depth + 1,
    show(Right, NewDepth),
    tab(3*Depth),
    writeln(Root),
    show(Left, NewDepth).

tree([19,
      [18,
       [12, [], []],
       [15, [], []]],
      [17,
       [10, [], []],
       [16, [], []]]]).

Some examples of insertion with a modified version of your code (notice that, in the second case, leaf 3 is not as far to the left as possible):

?- tree(Tree), insert(2, Tree, NewTree), show(NewTree).
      16
   17
      10
19
      15
   18
      12
         2
...

?- tree(T1), insert(2, T1, T2), insert(3, T2, T3), show(T3).
      16
   17
      10
         3
19
      15
   18
      12
         2
...

If the leaves in the last level of the tree do not need to be grouped on the left, a simple solution is:

simple_insert(Item, [], [Item, [], []]) :- !.
simple_insert(Item, [Root, Left, Right], [Root, Right, NewLeft]) :-
    simple_insert(Item, Left, NewLeft).

Here are some examples of insertion with this simple code:

?- foldl(simple_insert, [1,2,3,4,5,6,7], [], T), show(T).
      7
   3
      5
1
      6
   2
      4
...

?- tree(Tree), simple_insert(2, Tree, NewTree), show(NewTree).
         2
      12
   18
      15
19
      16
   17
      10
...

?- tree(T1), simple_insert(2, T1, T2), simple_insert(3, T2, T3), show(T3).
         3
      10
   17
      16
19
         2
      12
   18
      15
...

To solve the second problem, you should recall that a complete tree of height H must have 2^H - 1 nodes. Therefore, you should insert the new item in the right if, and only if, the left is a complete tree and the size of the right is less than the size of the left.

% quasi-complete tree insertion

qc_insert(Item, [], [Item, [], []]) :- !.
qc_insert(Item, [Root, Left, Right], NewTree) :-
    height(Left, Hl),
    size(Left, Sl),
    size(Right, Sr),
    (   (Sl =:= 2^Hl-1,  % Left is complete and
         Sr < Sl)        % Right has less items than Left
    ->  qc_insert(Item, Right, NewRight), 
        NewTree = [Root, Left, NewRight]
    ;   qc_insert(Item, Left, NewLeft), 
        NewTree = [Root, NewLeft, Right] ).

height([], 0).
height([_,L,R], H):-
   height(L, Hl),
   height(R, Hr),
   H is 1 + max(Hl, Hr).

size([], 0).
size([_,Left,Right], S) :-
    size(Left, Sl),
    size(Right, Sr),
    S is 1 + Sl + Sr.

Some examples of insertion with the correct code:

?- foldl(qc_insert,[1,2,3,4,5],[],T), show(T).
   3
1
      5
   2
      4
...

?- tree(Tree), qc_insert(2, Tree, NewTree), show(NewTree).
      16
   17
      10
19
      15
   18
      12
         2
...

?- tree(T1), qc_insert(2, T1, T2), qc_insert(3, T2, T3), show(T3).
      16
   17
      10
19
      15
   18
         3
      12
         2
...

One last observation is that it is better to represent trees using terms, instead of lists. So, for example, the tree [1, [2, [], []], []] should be represented as t(1, t(2, nil, nil), nil).