Prolog exercise 2-3-4 tree

Question

My prof gave me an exercise to do with prolog. Given this goal i have to build the corrispondent 234 tree:

write(tree(1,tree(11,tree(111,n,n),tree(112,tree(1121,n,n),n)),tree(12,tree(121,n,n),tree(122,n,n), tree(123,n,n),tree(124,tree(1241,n,n),tree(1242,n,n)))))

The result should be something like this:

Are you asking what is my problem ?

I studied what is a 234 tree, but i dont understand why the tree i represented can be considered a 234 tree, what i see are numbers that range from 1 to 1242. Should a 234 tree be something like this ?

Answer 1

Here's your given term, pretty printed for clarity:

tree(1,      % has 2 child nodes
      tree(11,       % has 2 child nodes
             tree(111,n,n),     % a leaf
             tree(112,          % has 2 child nodes
                     tree(1121,n,n),          % a leaf
                     n)),                     % empty
      tree(12,       % has 4 child nodes
             tree(121,n,n),     % a leaf
             tree(122,n,n),     % a leaf
             tree(123,n,n),     % a leaf
             tree(124,          % has two child nodes
                     tree(1241,n,n),          % a leaf
                     tree(1242,n,n))))        % a leaf

It is clear that the "numbers" 1, 11, 12, ..., 1242 aren't used for their numeric value, but just as stand-ins. In other words, the values are unimportant. A valid tree has already been built.

This tree's nodes each have either 2 or 4 child nodes (possibly empty, signified by n). That is why it is considered to be a 2-3-4 tree, where each node is allowed to have 2, 3, or 4 child nodes (possibly empty).

Your question then becomes, given a 2-3-4 tree represented by a Prolog compound term like the one above, print the tree in the nice visual fashion as shown in your attached image.

This is achieved simply by swapping the printing of nested sub-trees with the printing of the node's value:

print_tree( n ).
print_tree( tree(A,B,C) ) :- print_tree(B), 
                             print_node_value(A), 
                             print_tree(C).
print_tree( tree(A,B,C,D) ) :- print_tree(B), 
                             print_node_value(A), 
                             print_tree(C),
                             print_tree(D).
print_tree( tree(A,B,C,D,E) ) :- print_tree(B), 
                             print_tree(C),
                             print_node_value(A), 
                             print_tree(D),
                             print_tree(E).

You will have to augment this by passing in the desired indentation level, and incrementing it, by the same amount, when printing the child nodes.