Re: Depth First Search traversal of this list

On 2008-09-10, crashoverride111@xxxxxxxxx <crashoverride111@xxxxxxxxx> wrote:
Hello,
I am trying to traverse the list (A (B (D E) C)) in a way that the
print output should be in the following order D, E, B, C, A aka depth
first traversal.

This isn't depth-first traversal.

Depth first means: A B D E C, in other words, the left-to-right order in
which the nodes appear.

Breadth first means: A B C D E. The tree is traversed down to level N,
before proceeding to level N + 1.

What you are asking for is to visit level N + 1 before visiting level N.
This is not what is generally understood, in computer science, as
depth first.

This is almost like the output of a breadth-first traversal in reverse,
except that you still want to process each level left-to-right.

So we can start by coding a breadth-first traversal. This algorithm
works by iterating over the items at one level in the tree. Atoms
at the current level are visited in left-to-right order. Subtrees (i.e. conses)
are deferred into a queue, which is processed after the atoms are visited.

We append the list together, so for instance if we are processing
(A (B C) D (E F)) the algorithm will visit A, append (B C) to the queue, then
visit D, and append (E F) to the queue, so the queue holds (B C E F).
It will then recurse over the queue, visiting B C E F.

(defun breadth-first-map (function tree)
(loop for item in tree
if (consp item)
append item into queue
else
do (funcall function item)
finally
(unless (null queue)
(breadth-first-map function queue))))

Test cases:

(breadth-first-map #'print '(1 2 (3 (9 10) 4) 5 (6 7)))

-> NIL

[output]
1
2
5
3
4
6
7
9
10
[/output]

(breadth-first-map #'print '(A (B (D E) C)))

-> NIL

[output]
A
B
C
D
E
[/output]

So that is breadth-first traversal. What you are looking for is a traversal
which visits the levels in the reverse order: lower levels first. At each
level, it still visits the atoms in the left-to-right order.

To visit the lower level first, we cannot process the current level items
immediately as we see them. We must collect them into a list.

And we must still maintain a queue for visiting the next lower depth.

After collecting both the queue and current level items, we do the recursion to
the next depth first, and then map the saved current level items through the
function to visit them:

(defun breadth-first-map-bottom-up (function tree)
(loop for item in tree
if (consp item)
append item into queue
else
collect item into current-level-items
finally
;; recurse to lower depths first---
;; ---not to be confused with ``depth-first traversal''!!!
(unless (null queue)
(breadth-first-map-bottom-up function queue))
;; then process items at this level
(mapc function current-level-items)))

(breadth-first-map-right-left-bottom-up #'print '(A (B (D E) C)))

[output]
D
E
B
C
A
[/output]

So there is your so-called ``depth first'' traversal.
It doesn't appear to be a particularly useful invention.

One last note. Notice that the original breadth-first traversal is tail
recursive; it can be trivially rewritten as a loop. The last thing it does is
call itself, and doesn't do anything with the return value, other
than pass it up.

This means we can replace the recursive call by assigning to the parameters and
looping backwards. The null queue test which terminates the recursion becomes a
termination test for our loop. For the sake of variety, let's use DO, and move
the termination test into its termination clause:

(defun breadth-first-map (function tree)
(do () ((null tree)) ;; loop until tree is null
(loop for item in tree
if (consp item)
append item into queue
else
do (funcall function item)
finally
;; process next level by treating the
;; queue as the tree
(setf tree queue))))

Homework for you: is the bottom-up version of the traversal tail recursive?
Can we easily rewrite it to use iteration?
.

Relevant Pages

  • Re: Count all nodes in a treeview
    ... Which suggests that the TTreeNodes type exposes the entire tree as a flat hierarchy via its "Item" member. ... Pedro's code does this via recursion, returning for each node the sum of the number of direct descendants and the calculated value of nodes from each of those descendants. ... child I traverse the childnode and get all of it's settings too. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: factorial n! program
    ... advantages of not doing recursion. ... A depth-first tree ... traversal is just a loop around a stack. ... suppose you want to traverse the tree width-first? ...
    (comp.lang.fortran)
  • Re: Implementation of Trees
    ... I can traverse a tree without iterative programming (or even a stack, ... but it's debatable whether recursion or iteration is the obvious way ... Well you can think of a list as a special case of a tree, ...
    (comp.programming)
  • Re: Implementation of Trees
    ... I can traverse a tree without iterative programming (or even a stack, ... list with recursion. ...
    (comp.programming)
  • Re: Walk DOM Tree in Reverse?
    ... algorithm will traverse all nodes (sadly not necessarily visiting each ... the right child of the current root (plus at the beginning of the ... var fakeParent =!elem.parentNode; ... tree may be passed in. ...
    (comp.lang.javascript)