Depth First Search traversal of this list

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.

So far, I have come up with this code but it seems to have some strange problem.

(setq start (list 'a (list 'b (list 'd 'e) 'c )))           ====> gives ====> (A (B (D E) C))

(defun depth-first (start)
	(cond
		((null start) 0)
		((listp (first start)) (setq start (first start)) 
							   (depth-first (first start)))
		((not (eq nil (car start))) (print (car start))
					(setq start (rest start)) 
					(depth-first (start)))
		(t "Go home")))

Can someone please help me out.

Remember that your list looks like this (with depth going down):

(a, .............)
    (b, ....., c)
        (d e)

So do you want the output to be D, E, B, C, A? I thought it would be A, B, D, E, C. Breadth first would be A, B, C, D, E. I haven't done much of this kind of thing though, so I could be mistaken.

P.S. Your error is caused by you trying to call start as a function (see the second last line of your code).

This problem looks a bit homework-ish, so I will try not to reveal an answer outright, but also, I hope I don't come off too condescending.

What Kohath is talking about is the normal way we think of trees in CL. These are binary trees where the CAR is and the CDR are the two branches from an interior node. Only leaves hold values. You are looking to do something a bit different (perhaps, or perhaps you are confused).

Let me ask a question, how would you print this list: (A (B C) (D (E F)))? I am honestly not sure how this would be printed from your example. Better than hazarding guess, I will just ask and wait for a response.

(defun depth-first (start)
   (cond
      ((null start) 0)
      ((listp (first start)) (setq start (first start))
                        (depth-first (first start)))
      ((not (eq nil (car start))) (print (car start))
               (setq start (rest start))
               (depth-first (start)))
      (t "Go home")))

Looks like some clumsy assignments in there. There really is no reason for that on a problem like this.

My suggestion is to think this out in pseudo code first. Or, like I do, just pretend you are the computer walking along the tree. Develop a set of rules that you will follow at each point and see if it works for various inputs. Then you can sit down and start thinking about an algorithm that works for all inputs.

Zach S

crashoverride wrote: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 is a depth-based ordering of the nodes, but you need to collect elements breadth-first. Try writing a function that takes a tree as its only argument and returns a list of lists, where the nth element of the list is a list of all atoms at the nth level of the tree. You'll also need a function that combines two of those level lists into a single level list, and you'll have to massage the final list a little to get a flat bottom-up list.