Binary Tree Traversal, Part 1
Tags: picolisp, lisp, functional, algorithms
Published: 2021-12-09 09:50:18

In the last post, we discussed how [binary trees](https://picolisp-blog.hashnode.dev/picolisp-explored-the-idx-function) are created in PicoLisp. Now let's play a little more with them. See the following [task from the Rosetta Code](https://rosettacode.org/wiki/Tree_traversal#PicoLisp):

### 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](https://en.wikipedia.org/wiki/Tree_traversal) 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!**

![choppedtree.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1631698821200/WmDepGhHW.png)

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](https://picolisp-blog.hashnode.dev/60-picolisp-functions-you-should-know-6-lists-and-strings) 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](https://gitlab.com/picolisp-blog/single-plage-scripts/-/blob/main/rosetta/tree-traversal-part1.l).

-------------------------------

### Sources
- http://rosettacode.org/wiki/Tree_traversal