#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)