# Binary Tree Traversal, Part 1 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 )``.* 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