codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#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)
Private
[
?
]
Run code
Submit