In the last post, we discussed how binary trees are created in PicoLisp. Now let's play a little more with them. See the following task from the Rosetta Code:

### Task

Implement a binary tree where each node carries an integer, and implement:

- pre-order,
- in-order,
- post-order, and
- level-order traversal.
Use those traversals to output the following tree:

`1 / \ / \ / \ 2 3 / \ / 4 5 6 / / \ 7 8 9`

The correct output should look like this:

`preorder: 1 2 4 7 5 3 6 8 9 inorder: 7 4 2 5 1 8 6 9 3 postorder: 7 4 5 2 8 9 6 3 1 level-order: 1 2 3 4 5 6 7 8 9`

### Some thoughts about the task

The first thing we need to clarify is the meaning of "preorder", "inorder", "postorder" and "level-order". This Wikipedia article can help:

**preorder**: visit current node, traverse the left subtree, traverse right subtree.**inorder**traverse left subtree, visit current node, traverse right subtree.**postorder**traverse left subtree, traverse right subtree, visit current node.**level-order**(also called "breadth first search") the tree is broadened as much as possible before going to the next depth.

One key characteristic of binary trees is that a "large" binary tree is constructed from a repetitive pattern of "small" trees. This is very convenient for us: It means we can define the above four rules in a very simple way **by use of recursion**.

## Step 1. Defining the tree

We have learned in the previous post that a binary tree is represented as a nested list where the syntax is `(root (left-child) right-child)`

. Let's set a global variable `*Tree`

as list:

```
(setq *Tree
(1
(2 (4 (7)) (5))
(3 (6 (8) (9))) ) )
```

*You can double-check the tree structure in the REPL with (view <var>).*

Question: **Why didn't we use the idx function as learned in the previous post?** - Because the tree from the task is not a

*search*tree. In a search tree, the left child is supposed to be smaller, the right child larger than the root.

## The recursive nature of binary trees

Now we need to think a little bit about the nature of binary trees. We said before that a large binary tree is a *composition* of small binary trees. What does that mean exactly?

Look at the binary tree example from above and "chop" off the root. What do you get? **Two new binary trees!**

Together with the fact that binary trees are actually implemented as lists, this is a very handy characteristics. In lists we can access the first list element with the `car`

function, and all the rest with the `cdr`

-function. *(Go back to the List and Strings post if you forgot why).*

```
: (car *Tree)
-> (1)
: (cdr *Tree)
-> -> ( (2 (4 (7)) (5)) (3 (6 (8) (9))) )
```

Now we know that `2, 4, 7, 5`

forms one subtree, and `3, 6, 8, 9`

forms another subtree. This corresponds to the output of `(cdr *Tree)`

: `( (subtree 2-4-7-5) (subtree 3-6-8-9)`

.

This means: **if we do car and cdr on (cdr *Tree), we can get the subtrees on each side.**

Instead of `car (cdr ...)`

we can write `cadr`

, and instead of `cdr (cdr ..)`

, we can write `cddr`

. So let's use this:

```
: (cadr *Tree)
-> (2 (4 (7)) (5))
: (cddr *Tree)
-> ((3 (6 (8) (9))))
`
```

Looks almost good, only one minor modification is needed. `cddr`

returns a **list with only one item**. In order to get this single item, let's take the `car`

of `cddr`

, in short `caddr`

, for the right subtree:

```
: (caddr *Tree)
-> (3 (6 (8) (9)))
```

One last thing to mention is that the `car`

and `cdr`

functions do not modify the original `*Tree`

. We merely move the pointers around. This means, these functions are **not destructive**:

```
: *Tree
-> (1 (2 (4 (7)) (5)) (3 (6 (8) (9))))
```

### ...and recurse!

Let's double-check the recursive nature of our tree. Let's take the left subtree, `2-4-7-5`

. Again, we get the **node** by `car`

, the **left subtree** by the `cadr`

and the **right subtree** by `caddr`

:

```
: (car (cadr *Tree))
-> 2
: (cadr (cadr *Tree))
-> (4 (7))
: (caddr (cadr *Tree))
-> (5)
```

If we try to access a breach that does not exist, we get `NIL`

.

```
: (caddr (caddr (cadr *Tree)))
-> NIL
```

## Step 2. Defining the functions

Now comes the interesting part - how can we use this recursive nature to solve the pre-order task? Well, the definition from above already tells us how to do it:

preorder: visit current node, traverse the left subtree, traverse right subtree.

Let's define a function `preorder`

, with an argument `Tree`

(which is a list, as we know now). If `Tree`

is defined, let's print its root:

```
(de preorder (Tree)
(printsp (car Tree)
....
```

Now we want to "traverse the left subtree", and if there is a left child, we print it. And then we take again the left child, if available. If there is no left child, we return `NIL`

and try the right side next. Well, and that's already all there is to do.

```
(de preorder (Tree)
(when Tree
(printsp (car Tree))
(preorder (cadr Tree) )
(preorder (caddr Tree) ) ) )
```

The function returns `1 2 4 7 5 3 6 8 9`

.

Now it is easy to define `inorder`

and `postorder`

. Basically, they are just variations in order.

inorder: traverse left subtree, visit current node, traverse right subtree.

```
(de inorder (Tree)
(when Tree
(inorder (cadr Tree))
(printsp (car Tree))
(inorder (caddr Tree)) ) )
```

postorder: traverse left subtree, traverse right subtree, visit current node.

```
(de postorder (Tree)
(when Tree
(postorder (cadr Tree))
(postorder (caddr Tree))
(printsp (car Tree)) ) )
```

## Step 3. Calling the functions

Last step is to call the functions and get the output.

```
(printsp 'preorder:)
(preorder *Tree)
(prinl)
(printsp 'inorder:)
(inorder *Tree)
(prinl)
(printsp 'postorder:)
(postorder *Tree)
(prinl)
```

The code above is working, but very redundant with all its `printsp`

and `prinl`

. Let's try to improve it. We can simply pack all three functions in a list and loop through it:

```
(for Order '(preorder inorder postorder)
(prin Order ": ")
(Order *Tree)
(prinl) )
```

*As you can see, Order can both work as string to be printed, or as function name. This is one of the nice things you can do in functional languages!*

Output:

```
preorder: 1 2 4 7 5 3 6 8 9
inorder: 7 4 2 5 1 8 6 9 3
postorder: 7 4 5 2 8 9 6 3 1
```

### Wrap-Up

So far, so good. However, we are not done yet: The `level-order`

traversal route is missing. But before we do that, we will first study another interesting function that might help us wth that: the `fifo`

function.

You can download the finished code up to this point here.