An implementation of depth first search for recurse center interview

dfs.rkt

; Annie Cherkaev, Dec 29th 2015
#lang racket

; An implementation of depth first search
; Trees are represented as lists, where the first element is the 'name' of the node, and the rest of the list is the children of that node
; ie:     a
;        / \
;       b   c
; is represented as (a (b) (c))
; 
; If the target node is present in the tree, that node is returned
; Otherwise, an empty list is returned
(define (dfs queue target-node)    
  (if (not (empty? queue))                    ; do we have more nodes to check?
      (let  ([node (first queue)])            ; if so, grab the first node off the queue                     
        (if (eq? (first node) target-node)    ; and check the "name" of the node, which is the first element. did we find our target?
            node                              ; yes? return it!            
            (dfs (append (rest node) (rest queue)) target-node)))  ;recurse: the queue is now the children of the current node PREPENDED (bc dfs) to the existing queue
      (list)) ;this is the "fail" condition- if the node wasn't found, just return an empty node with no children... aka a new list   
  )

; A convenience wrapper with a non-empty tree check (to prevent an error on the "first" call in dfs)
(define (search tree target-node)
  (if (not (empty? tree))
      (dfs (list tree) target-node) ; initialize the queue to have the root node on it
      (list) ;fail condition
      ))


;; A copy of dfs that prints each node it traverses for testing that search is actually in depth-first order
(define (depth-test-dfs queue target-node)    
    (if (not (empty? queue)) 
        (let  ([node (first queue)])
          (display node)
          (display "\n")
          (if (eq? (first node) target-node)    
              node                                          
              (depth-test-dfs (append (rest node) (rest queue)) target-node)))  
        (list)))
  
 

; Tests!
; ================================================================================================================

(define test-tree '(a (b (d) (e) (f)) (c (g (h)))))
; that is:         a
;                 / \
;                b   c
;               /|\  |
;              d e f g
;                    |
;                    h


; can it find the root?
(equal? (search test-tree 'a) '(a (b (d) (e) (f)) (c (g (h)))))
; can it find a leaf-node on the first pass?
(equal? (search test-tree 'd) '(d))
; can it find a node deeper in the tree?
(equal? (search test-tree 'c) '(c (g (h))))
(equal? (search test-tree 'h) '(h))

; and a few more for good measure
(equal? (search test-tree 'g) '(g (h)))
(equal? (search test-tree 'e) '(e))
(equal? (search test-tree 'b) '(b (d) (e) (f)))



; what about a node not in the tree?
(equal? (search test-tree 'x) '())
; what about a tricky empty tree?
(equal? (search '() 'x) '()) 



;check dfs order by displaying the order we check the nodes in searching for a target node that does not exist in the tree
(depth-test-dfs (list test-tree) 'x)   ;(notice we pass test-tree wrapped in a list bc I didn't want to replicate the 'search' wrapper that did this for us with dfs)