```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 ``` ```#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) ```