Search code examples
recursionprologbinary-tree

Prolog number of nodes at a given depth in a tree

I am new to Prolog. I am trying to write a predicate which returns the number of nodes of a binary tree at a given depth in the tree. For example, the following tree

enter image description here

has 1 node of depth 0 (the root node), 2 nodes of depth 1, 3 nodes of depth 2 and 3 nodes of depth 3.

In my program, binary trees are represented as lists of the form [value, left-child, right-child], where left and right children can themselves be represented the same way. For example, here is the representation of the above tree:

[8, [3, [1, [], []], 
        [6, [4, [], []], 
            [7, [], []]]], 
    [10, [], 
         [14, 
            [13, [], []], 
            []]]]

Here is what I've come up with so far:

nbNodes([_,_,_],1,0).
nbNodes([_,LC,RC],N2,D2) :- 
    nbNodes(LC,NL,D), nbNodes(RC,NR,D), N2 is NL+NR, D2 is D+1.

Based on my limited understanding of Prolog, this means that:

  1. Every tree has only one node of depth 0.
  2. The number of nodes of depth D2 in a tree is the sum of the number of nodes of depth D2-1 in the left and right child of the three.

    Both assumptions seem correct.

However, when I test my code, the numbers returned (if any) are wrong. For example, the following code outputs "false" instead of "3":

nbNodes([8, [3, [1, [], []], [6, [4, [], []], [7, [], []]]], [10, [], [14, [13, [], []], []]]], N, 2).

What am I doing wrong ? Many thanks in advance.

Solution

  • How about

    nbNodes( [],0,_).
nbNodes( [_,_,_],1,0).
nbNodes( [_,LC,RC],N2,D2):-
    D2 > 0,
    D is D2-1,
    nbNodes( LC,NL,D), 
    nbNodes( RC,NR,D), 
    N2 is NL+NR.

    That is the result:

    ?- T = [8,[3,[1,[],[]],[6,[4,[],[]],[7,[],[]]]],[10,[],[14,[13,[],[]],[]]]],
   nbNodes(T,N,0).
T = [8, [3, [1, [], []], [6, [4, []|...], [7|...]]], [10, [], [14, [13|...], []]]],
N = 1 ;
false.
    
?- T = [8,[3,[1,[],[]],[6,[4,[],[]],[7,[],[]]]],[10,[],[14,[13,[],[]],[]]]],
   nbNodes(T,N,1).
T = [8, [3, [1, [], []], [6, [4, []|...], [7|...]]], [10, [], [14, [13|...], []]]],
N = 2 ;
false.
    
?- T = [8,[3,[1,[],[]],[6,[4,[],[]],[7,[],[]]]],[10,[],[14,[13,[],[]],[]]]],
   nbNodes(T,N,2).
T = [8, [3, [1, [], []], [6, [4, []|...], [7|...]]], [10, [], [14, [13|...], []]]],
N = 3 ;
false.
    
?- T = [8,[3,[1,[],[]],[6,[4,[],[]],[7,[],[]]]],[10,[],[14,[13,[],[]],[]]]],
   nbNodes(T,N,3).
T = [8, [3, [1, [], []], [6, [4, []|...], [7|...]]], [10, [], [14, [13|...], []]]],
N = 3 ;
false.

?- T = [8,[3,[1,[],[]],[6,[4,[],[]],[7,[],[]]]],[10,[],[14,[13,[],[]],[]]]], 
   nbNodes(T,N,4).
T = [8, [3, [1, [], []], [6, [4, []|...], [7|...]]], [10, [], [14, [13|...], []]]],
N = 0.

    The two major changes are that

    1. I added a clause for empty binary trees.
    2. I calculated D from D2, before I call the predicate again and do not calculate D2 from D after the recursive calls.

    I guess you are asking what the difference is, because you have been told that Prolog is declarative and thus we need to only specify what is the case (our knowledge base) and not how something can be inferred from our knowledge.

    Well, you have been lied at. Prolog is not purely declarative, since there is an order, in which it searches for an answer.

    If you want to prove a goal G by the use of a clause

    G :- L1,L2,L3.

    Prolog tries to prove L1, then L2, then L3 - although from a logical view, this clause says nothing but

    IF L1 and L2 and L3 THEN G,

    which is logically equivalent to

    IF L3 and L1 and L2 THEN G

    There might be a proof, if Prolog checked all possible orders, yet it doesn't.

    In addition, for many predicates, certain arguments need to be instantiated in order for the predicates to work. One of such predicates is is/2. Its right hand side needs to be fully instantiated for is/2 to work.

    Your predicate needs its third argument to be instantiated. When you call nbNodes(LC,NL,D) and nbNodes(RC,NR,D), D is not instantiated. Even if you changed the order of your clauses and put D2 is D+1 before those clauses, this doesn't work, since is/2 needs its right hand side to be fully instantiated, and D is not yet instantiated at that point.

    Try asking ?- X is 2. and ?- 2 is X. to see the difference.

    For a fuller picture, you need to dig into Prolog's (partial) implementation of the resolution principle. If you want to have a more declarative kind of Prolog, have a look at Constraint Logic Programming.