tree-path.rkt

tree-path.rkt

#lang racket

;; tree-path :: tree? -> any/c -> (listof (or/c 'here 'left 'right))
(define (tree-path t elt)
  (let loop ([t t] [out '()])
    (match t
      ['empty '()]
      [`(node ,(== elt) ,_ ,_) (reverse (cons 'here out))]
      [`(node ,_ ,l ,r)
       (match (loop l (cons 'left out))
         ['() (loop r (cons 'right out))]
         [left-result left-result])])))

(module+ test
  (require rackunit)
  (check-equal? (tree-path 'empty 1) '())
  (check-equal? (tree-path '(node 1 empty empty) 1) '(here))
  (check-equal? (tree-path '(node 1 empty empty) 2) '())
  (check-equal? (tree-path '(node 2 (node 1 empty empty) empty) 1)
                '(left here))
  (check-equal? (tree-path '(node 2 empty (node 1 empty empty)) 1)
                '(right here))
  (check-equal? (tree-path '(node 2 (node 1 empty empty) (node 1 empty empty)) 1)
                '(left here)))