[SOLVED] EECS-3401A ASSIGNMENT 1

Part I [20pt]: Dr. Dogfurry’s Binary Tree

Dr. Dogfurry has designed the following binary-tree data-structure in Prolog. A “node” term looks like

[bt(integer, binary_tree_node, binary_tree_node)] or []

The latter represents an empty tree. The former, a tree; the second and third arguments are

binary-tree nodes. Call the first argument, an integer, the node’s key.

A binary-tree node can have a left-child binary tree (the second argument) or a right-child binary tree (the third argument), or both. (If it does not have one or the other, an empty binary tree, [], is placed there.)

E.g., [bt(5, [], [bt(7, [], [])])]

For the forllowing, you may assume any term argument that you are passed is a proper binary tree, apropos Dr. Dogfurry’s representation:

it is finite (that is, does not contain circular “pointers”);

if it is not the empty binary tree, that the first argument is an integer, and the next two arguments are proper binary trees (maybe empty); and

that it is ground.

Q1. [5pt] empty_bintree/1

Write a procedure for empty_bintree/1 that takes an argument Tree. It should return true if this is an empty binary tree, apropos Dr. Dogfurry’s representation; and false (fail), otherwise.

The procedure should return true — with the appropriate additional behaviour — with an

unbound variable for its argument.

Q2. [5pt] bintree_contains/2

Write a procedure for bintree_contains/2 that takes two arguments, Key and Tree, in that order. The latter argument is input.

The procedure should evaluate true iff Key is equal to the key of any node in the binary tree