#lang racket

;;See http://programmingpraxis.com/ for details.

;;To Find the Least Common Ancestor  of two given elements m and n of a tree.
;;Tree need not be a binary tree i.e it could have more than two branches.
;;There is no constraint on m and n as long as they are elements of tree.

;;We represent the tree using hash table.
;;we represent the tree upside down i.e child to parent.
(define tree (make-hash))

;;takes a relation rep of tree and stores it 
;;in hash table. 
(define (make-tree rels root)  
  (begin
    (hash-set! tree root root)
  (for-each 
   (lambda (rel)
     (hash-set! tree (second rel) (first rel)))
   rels)))


;;parent of node in a tree.
(define (get-parent n)
  (hash-ref tree n #f))


;;This works by following the path
;;from m to root , and mark them visited.
;;Next we follow path from n to root , and
;;if we find a node that is already marked 
;;visited , then it is the lca of m and n.
(define (lca m n)
  
  (define mark (make-hash))
  
  (define (marked? n)
    (hash-ref mark n #f))
  
  (define (mark-elem n)
    (hash-set! mark n #t))
  
  (define (mark-path m)
    (let ([parent (get-parent m)])
      (begin
        (mark-elem m)
        (unless (equal? m parent)
          (mark-path parent)))))
  
  (define (get-common n)
    (if (marked? n)
        n
        (get-common (get-parent n))))
  
  (begin
    (mark-path m)
    (get-common n)))


;;simple rep of tree
(define a-tree '((8 3) (8 10) (3 1) (3 6) (6 4) (6 7) (10 14) (14 13)))

;;make a hash of it
(make-tree a-tree 8)

;runs
(= (lca 3 3) 3)
(= (lca 10 4) 8)
(= (lca 4 7) 6)
(= (lca 4 10) 8)
(= (lca 1 4) 3)
(= (lca 1 3) 3)
(= (lca 3 6) 3)