# .css-df1pn7{display:block;width:16rem;}     # Binary Tree Traversal, Part 1

## Pre-order, post-order, in-order

Mia Temma
·Sep 24, 2021·

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:

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
``````

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
-> (4 (7))
-> (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 (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
(printsp (car Tree))
``````

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

``````(de postorder (Tree)
(when 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.