Defining a Tree in LISP (Racket)

Question

I'm trying to define a tree using Racket's #plai language, though I'm struggling a bit when it comes to creating the tree through an "add-node" function.

The define-type I'm using goes like this:

(define-type BBT
  [empty]
  [leaf (elem number?)]
  [node (elem number?) (left BBT?) (right BBT?)])

And I'd like to construct a tree that looks like this:

(node 3 (empty) (node 5 (leaf 4) (leaf 6)))

Following this call:

(add-node 6 (add-node 4 (add-node 5 (add-node 3 (empty)))))

So far, I've tried the following:

(define (add-node n tree)
  (match tree
    [(empty) (node n (empty) (empty))]))

And that works for an empty tree, as it just adds a single node with empty trees at both sides, but I haven't found a way to construct a tree like the example I shared above.

Any tips or suggestions as to what should I do? I know I should use recursion when it catches the "node" case, but so far I haven't come up with a successful attempt.

Thanks!

Answer 1

From your example:

(add-node 6 (add-node 4 (add-node 5 (add-node 3 (empty)))))

is supposed to produce

(node 3 (empty) (node 5 (leaf 4) (leaf 6)))

This contains many calls to add-node, and that makes it more confusing. So to get a better idea of what you want, I'll start with the innermost call to add-node.

(add-node 3 (empty))

From the initial code in your question, it seems this should produce

(node 3 (empty) (empty))

So now replacing the innermost call in your larger example, it becomes

(add-node 6 (add-node 4 (add-node 5 (node 3 (empty) (empty)))))
=
(node 3 (empty) (node 5 (leaf 4) (leaf 6)))

Now I have to figure out what the next-innermost call is supposed to do.

(add-node 5 (node 3 (empty) (empty)))

In the final output the 3 stays on top and the 5 goes to the right node, so I can only guess that this call is supposed to produce

(node 3 (empty) (node 5 (empty) (empty)))

Now replacing that call in the larger example:

(add-node 6 (add-node 4 (node 3 (empty) (node 5 (empty) (empty)))))
=
(node 3 (empty) (node 5 (leaf 4) (leaf 6)))

The next innermost call is

(add-node 4 (node 3 (empty) (node 5 (empty) (empty))))

Now this is where I don't understand your logic. By the pattern of the previous example, the 4 should go into the rightmost node, "right-right". But in this example it seems to go in the left portion of the right node, "right-left". It doesn't seem to be going to the nearest empty node, which would be pure "left", so I don't know what pattern you're trying to make.

Please clarify your question and add more specifics if you want a better answer.

Answer 2

In the end, I found out a way to construct the tree like this:

(define (add-node n tree)
  (match tree
    [(empty) (node n (empty) (empty))]
    [else (add-aux n tree)]))

(define (add-node-aux n tree)
  (match tree
    [(empty) (leaf n)]
    [(leaf e) (if (> e n)
                  (node e (leaf n) (empty))
                  (node e (empty) (leaf n)))]
    [(node e l r) (if (> e n)
                    (node e (add-node-aux n l) r)
                    (node e l (add-node-aux n r)))]))

It does the job but I was wondering if there's a way to create the tree without relying on the auxiliary function. Basically, I created the auxiliary call to prevent having trees with just one node (Root trees) being labeled as "leaves". So, instead of having the first element output a tree with shape (leaf 3), by calling the recursive function, it's possible to get a tree like (node 3 (empty) (empty)).

Is there a way I could do this without making the auxiliary call?

Thanks!