Finding the binary tree height in Prolog

Question

So I have a task to create a binary tree using the following facts that define each node with its two child nodes:

node(root, a, b).
node(a, c, d).
node(b, z, y).
node(c, e, f).
node(d, x, w).
node(e, g, h).
node(z, v, u).
node(u, t, s).
node(t, r, q).

I want to define the rule height(RootNode, Height) to calculate the height of the binary tree that starts at the RootNode. The height of a tree is the longest distance (number of nodes) from the root node to the farthest away leaf node. A leaf node is a node that doesn’t have any children. The height of a leaf node is 1.

The code I currently have is:

node(root, a, b).
node(a, c, d).
node(b, z, y).
node(c, e, f).
node(d, x, w).
node(e, g, h).
node(z, v, u).
node(u, t, s).
node(t, r, q).

height(nil, 0).
height(RootNode, Height):-
    node(RootNode, Left, Right),
    height(Left, LH),
    height(Right, RH),
    Height is max(LH, RH) + 1.

At the moment, I'm really stuck and would love to know what happens to this code when it runs, why I've done this incorrectly and where I should look to improve further? Appreciate any help.

what is nil? what is f? should it be node(c, e, nil). or node(f, nil, nil).? — Will Ness
also, you've included your facts twice. one time is enough, no need to repeat them. you can edit to remove the excess code. — Will Ness
These were the rules that were given to me, so it must be like this — Dylan

gusbro gusbro · Accepted Answer · 2020-11-12T15:55:01

The problem with your code is that your base case requires that each leaf node exists in the database in the form node(Leaf, nil, nil) but according to your example leaf nodes are just nodes that appear as the second or third argument of a node/3 fact but does not appear as the first argument of another node/3 fact.

So you may fix your code by changing your base case:

instead of

height(nil, 0).

use

height(Leaf, 1):-
  \+node(Leaf, _, _).

(note that the base case has height 1 as per your description)

Test case:

?- height(root,A).
A = 6 ;
false.

You may also "join" both clauses in a single one:

height(RootNode, Height):-
    node(RootNode, Left, Right) *->
    (height(Left, LH),
    height(Right, RH),
    Height is max(LH, RH) + 1) ; Height = 1.

test run:

?- height(root,A).
A = 6.

Finding the binary tree height in Prolog

1 Answers