title: Defining a Tree in LISP (Racket)
body: <p>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.</p>
  
  <p>The define-type I'm using goes like this:</p>
  
  <pre><code>(define-type BBT
    [empty]
    [leaf (elem number?)]
    [node (elem number?) (left BBT?) (right BBT?)])
  </code></pre>
  
  <p>And I'd like to construct a tree that looks like this:</p>
  
  <pre><code>(node 3 (empty) (node 5 (leaf 4) (leaf 6)))
  </code></pre>
  
  <p>Following this call:</p>
  
  <pre><code>(add-node 6 (add-node 4 (add-node 5 (add-node 3 (empty)))))
  </code></pre>
  
  <p>So far, I've tried the following:</p>
  
  <pre><code>(define (add-node n tree)
    (match tree
      [(empty) (node n (empty) (empty))]))
  </code></pre>
  
  <p>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. </p>
  
  <p>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.</p>
  
  <p>Thanks!</p>