DEV Community

Cover image for Binary Tree Traversal, Part 2
Mia
Mia

Posted on • Originally published at picolisp-explored.com

3 2

Binary Tree Traversal, Part 2

Welcome back to the second part of the "Binary tree traversal" task from Rosetta Code. This is a follow up to part 1.

We have solved everything except for the level-order traversal.


The level-order traversal

As a reminder, we are looking at the following tree:

         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9
Enter fullscreen mode Exit fullscreen mode

What we want to get is the output from top to bottom and left to right: 1 2 3 4 5 6 7 8 9. This means that we will visit each level and get the output.


Yesterday we discussed the fifo function as a little preparation for solving this task. The fifo function allows us to create a queue from which we always take out the oldest item.

Creating the queue

But what are our queue items?

  1. At first, we only have one item in the queue: The full tree.
  2. Then we take the tree root, which means we have two trees left: The left and right tree. These are put in the waiting queue.
  3. Then we take out the first tree in the queue and take the root.
  4. Again, we queue up its left and right trees.
  5. And so on.

In the animation below, you can get an impression how the algorithm works.

treegif.gif

Unfortunately, this time it is easier to draw it on paper than to write it as code. Let's try. Reminder: We can get the left subtree with (cadr *Tree) and the right subtree with caddr *Tree.


The first round

We know that we want to put our binary tree into a fifo list. A fifo list is circular. In order to use the fifo function, we need a variable to store our queue. So let's define a variable Q (like "queue") and store the queued items there. We can make it circular with the circ function.

In the beginning, there is only a single item: The whole tree.

: (setq Q (circ *Tree))
-> ((1 (2 (4 (7)) (5)) (3 (6 (8) (9)))) .)
Enter fullscreen mode Exit fullscreen mode

Now we can apply what we learned about the fifo function.
Let's take the first item in the queue with fifo <list> and store it in a variable N:

: (setq N (fifo 'Q))   
-> (1 (2 (4 (7)) (5)) (3 (6 (8) (9))))
Enter fullscreen mode Exit fullscreen mode

As expected, our fifo list only had one item which was the full tree. Now the queue is empty again.

Let's print out the root, just like we did in the recursive tree traversal functions. The node is simply the car.

(printsp (car N))
Enter fullscreen mode Exit fullscreen mode

Now we want to add the left and right subtree to the queue, if they exist. The syntax for adding new items to a fifo list is fifo <list> <item>.

The existence check and subsequent adding can be written like this:

(when (cadr N) (fifo 'Q @))
(when (caddr N) (fifo 'Q @)) ) ) )
Enter fullscreen mode Exit fullscreen mode

@ is a short symbol for the result of the conditional
expression when we evaluate flow functions. We could have as well written (cadr N) and (caddr N).

Now we have two new items in the queue: the left subtree and right subtree. What next?


...and the rest

This is what we have now in our queue:

: Q
-> ((3 (6 (8) (9))) (2 (4 (7)) (5)) .)
Enter fullscreen mode Exit fullscreen mode

So what we basically need is a so-calledfor loop that runs until Q is empty. If you followed the previous posts carefully, this might remind you of the "100 Doors" task, where we had a similar topic (= executing our actions as long as the "Doors"-list was not empty).

In this case, we used the "third form of the for loop" (check the docs), which takes three parameters: A symbol that we use in the loop, a list to which this symbol is bound, and an exit condition. The loop is executed as long as the exit condition is non-NIL.

So let's bound Q to the circular Tree-List. The loop should stop when Q is NIL. Like this:

(for (Q (circ Tree)  Q)
Enter fullscreen mode Exit fullscreen mode

Now we just have to put it together:

(de level-order (Tree)
   (for (Q (circ Tree)  Q)
      (let N (fifo 'Q)
         (printsp (car N))
         (when (cadr N) (fifo 'Q @))
         (when (caddr N) (fifo 'Q @)) ) ) )
Enter fullscreen mode Exit fullscreen mode

We call it and get (level-order: 1 2 3 4 5 6 7 8 9). Finished!


The final code can be downloaded here.


Sources

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay