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.
Sources
http://rosettacode.org/wiki/Tree_traversal
