Skip to content

Instantly share code, notes, and snippets.

@shakdwipeea
Last active June 12, 2020 12:45
Show Gist options
  • Save shakdwipeea/58f0f2e019625a44be5a5ab91b898f72 to your computer and use it in GitHub Desktop.
Save shakdwipeea/58f0f2e019625a44be5a5ab91b898f72 to your computer and use it in GitHub Desktop.
(def e {:name "E"})
(def f {:name "F"})
(def c {:name "C" :left e :right f})
(def d {:name "D"})
(def b {:name "B" :left d})
(def a {:name "A" :left b :right c})
(def i {:name "I"})
(def j {:name "J"})
(def h {:name "H" :left i :right j})
(def g {:name "G" :left h})
(def root {:name "Object" :left a :right g})
(defn mark-parent [node parents]
(letfn [(add-parent-data [p cur]
(let [parent-name (keyword (:name node))]
(distinct (concat (get parents parent-name)
p
(list parent-name (keyword (:name cur)))))))]
(if (and (nil? (:left node)) (nil? (:right node)))
parents
(merge (when (:left node)
(mark-parent (:left node) (update parents
(keyword (:name (:left node)))
(fn [p]
(add-parent-data p (:left node))))))
(when (:right node)
(mark-parent (:right node) (update parents
(keyword (:name (:right node)))
(fn [p]
(add-parent-data p (:right node))))))))))
(def parent-data (mark-parent root {}))
(defn find-common-ancestor [class1 class2]
(let* [parents1 (class1 parent-data)
parents2 (class2 parent-data)
longer-parent (if (> (count parents1) (count parents2))
parents1
parents2)
shorter-parent (if (> (count parents1) (count parents2))
parents2
parents1)]
(loop [p (reverse longer-parent)
c (first shorter-parent)]
(if (some (fn [p0] (= p0 (first p))) (seq shorter-parent))
(first p)
(recur (rest p) c)))))
(= (find-common-ancestor :E :F) :C)
(= (find-common-ancestor :D :F) :A)
(= (find-common-ancestor :I :J) :H)
(= (find-common-ancestor :H :J) :H)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment