#lang racket

(define-struct binary-tree (root left right))

(define immediate-ancestor (make-hash))

(define (make-ancestor tree ancestor)
  (cond
   [(empty? tree) (void)]
   [else (hash-set! immediate-ancestor (binary-tree-root tree) ancestor)
	 (make-ancestor (binary-tree-left tree) (binary-tree-root tree))
	 (make-ancestor (binary-tree-right tree) (binary-tree-root tree))]))

(define (get-ancestor k)
  (hash-ref immediate-ancestor k #f))

(define (get-common m n)
  
  (define mark-visited (make-hash))
  
  (define (set-path-m m)
    (let ([ancestor (get-ancestor m)])
      (hash-set! mark-visited m #t)
      (unless (equal? ancestor m)
        (set-path-m ancestor))))
       
  (define (get-common1 n)
    (let ([ancestor (get-ancestor n)])
      (if (hash-ref mark-visited n #f)
          n
          (get-common1 ancestor))))
  
  
  (set-path-m m)
  (get-common1  n))

(define btree
  (make-binary-tree
   8
   (make-binary-tree
    3
    (make-binary-tree 1 empty empty)
    (make-binary-tree 
     6
     (make-binary-tree 4 empty empty)
     (make-binary-tree 7 empty empty)))
   (make-binary-tree
    10
    empty
    (make-binary-tree
     14
     (make-binary-tree
      13
      empty
      empty)
     empty))))


(make-ancestor btree (binary-tree-root btree))

(get-common 4 7)
(get-common 4 10)
(get-common 1 4)
(get-common 1 3)
(get-common 3 6)