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

Question

To add a new element to the heap we must:

1. Create a node containing the value of this element,
2. Tie this knot in the last level in the first empty place as far to the left as possible (create a new level if necessary). We always get a complete binary tree, but not necessarily a heap.

I wrote this code:

insert(I, [], [I, [], [] ] ).
insert(I, [_, G, D], N):-
   depth(G, P1), depth(D, P2), P1<P2, insert(I, G, N).
insert(I, [_, G, D], N):-
   depth(G, P1), depth(D, P2), P1>P2, insert(I, D, N).

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

but when this query is executed, it fails:

?- insert(2, [19, [18, [12, [], []], [15, [], []]], [17, [10, [], []], [16, [], []]]], N).
false.

Why?

Answer 1

((You do not define max/3 in your program. I guessed it to be the following))

max(A, B, M) :-
   M is max(A,B).

Why?

First, always start with small examples. Like a tree with a single element. That fails as well:

?- insert(2, [12, [], []], N).
false.

So why? If a (pure, monotonic) program fails, then we need to generalize it. Let's try this like so:

:- op(950, fy, *).
*(_).

insert(I, [], [I, [], [] ] ).
insert(I, [_, G, D], N):-
   depth(G, P1),
   depth(D, P2),
   P1<P2,
   * insert(I, G, N).
insert(I, [_, G, D], N):-
   depth(G, P1),
   depth(D, P2),
   P1>P2,
   * insert(I, D, N).

So these recursive goals have been removed by adding a * in front, clearly a generalization that goes too far. Yet, the query still fails! So these P1<P2, P1>P2 comparisons seem to be the culprit. What happens if they are the same? Then both rules do not apply. So you clearly forgot to consider this case.

But there is another problem, let's ignore these comparisons and see what happens then:

insert(I, [], [I, [], [] ] ).
insert(I, [_, G, D], N):-
   depth(G, P1),
   depth(D, P2),
   * P1<P2,
   insert(I, G, N).
insert(I, [_, G, D], N):-
   depth(G, P1),
   depth(D, P2),
   * P1>P2,
   insert(I, D, N).

?- insert(2, [12, [], []], N).
   N = [2,[],[]]
;  N = [2,[],[]].
?- insert(2, [19, [18, [12, [], []], [15, [], []]], [17, [10, [], []], [16, [], []]]], N).
   N = [2,[],[]]
;  N = [2,[],[]]
;  N = [2,[],[]]
;  N = [2,[],[]]
;  N = [2,[],[]]
;  N = [2,[],[]]
;  N = [2,[],[]]
;  N = [2,[],[]].

Can this be right? No matter what tree we are using to start with, we will always get a single solution back. So regardless of the place where you want to insert the new element, you would have to address this problem, too.

And if I am at at, consider to use clpfd via library(clpz) or its slightly outdated predecessor library(clpfd) in place of (>)/2 etc. since this does not give you so many errors.

See this answer for more debugging methods specific to Prolog.