Problem 7: Find It! III (optional, 0pts)
Implement the find-in-tree
procedure, which takes a Scheme tree t
, a target value goal
and returns a list containing all paths from the root of t
to all node containing goal
. If no such path exists, find-in-tree
returns an empty list. The return list should be sorted by the end of each path, according to preorder traversal order.
(define (find-in-tree t goal)
'YOUR-CODE-HERE
)
;;; Tests
; A tree for test
(define t1 (tree 1
(list
(tree 2
(list
(tree 3 nil)
(tree 7 (list
(tree 7 nil)))))
(tree 3 nil)
(tree 6
(list
(tree 7 nil))))))
; scm> (find-in-tree t1 0)
; ()
; scm> (find-in-tree t1 2)
; ((1 2))
; scm> (find-in-tree t1 3)
; ((1 2 3) (1 3))
; scm> (find-in-tree t1 7)
; ((1 2 7) (1 2 7 7) (1 6 7))