20 Feb 2013

Since a friend has just raised the question, “Find the deepest node in a binary tree,” here’s my Clojure-flavoured answer:

(defn leaf?
  [node]
  (not (map? node)))
(defn deepest
  [node]
  (if node
    (if (leaf? node)
      [0 node]
      (let [[depth leaf] (last (sort [(deepest (:left node))
                                      (deepest (:right node))]))]
        [(inc depth) leaf]))))

And here it is in action:

(deepest {:left "A"
          :right {:left {:left "B"
                         :right "C"}
                  :right "D"}})
| 3 | C |

His response? “It’s a bit longer in C++.”

comments powered by Disqus