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
– Will Ness, Commented Nov 12, 2020 at 15:53
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
– Will Ness, Commented Nov 12, 2020 at 15:55
These were the rules that were given to me, so it must be like this — Dylan
– Dylan, Commented Nov 12, 2020 at 15:56

gusbro · Accepted Answer · 2020-11-12 15:55:01Z

2

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.

answered Nov 12, 2020 at 15:55

gusbro

22.6k39 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Will Ness Over a year ago

why *-> ? you allow for more than one node with the same identifier?

gusbro Over a year ago

To allow using an unbound variable as the first argument to height/2

gusbro Over a year ago

@WillNess: calling height(Node, Height) won't return leafs though in the "joined" procedure

Dylan Over a year ago

Thank you for the answer, appreciate that. So, it was just my base case that wasn't correct? If so, does it read: The leaf node height is equal to 1 if the leaf node doesn't have any more leaf nodes?

gusbro Over a year ago

@Tw1sssted: Yes, the base case was not correct. A leaf node is, by definition, a node which does not have children. So it would read: a node height is equal to 1 if the node does not have any children.

|

Collectives™ on Stack Overflow

Finding the binary tree height in Prolog

1 Answer 1

6 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Related