Skip to content

Instantly share code, notes, and snippets.

@michaelayoub

michaelayoub/level_order_traversal.clj

Created June 19, 2025 21:52
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save michaelayoub/144e1f6334ef2a47f9cd16c4f4809069 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save michaelayoub/144e1f6334ef2a47f9cd16c4f4809069 to your computer and use it in GitHub Desktop.
Download ZIP
Clojure level-order traversal (2025-01-04)
Raw
level_order_traversal.clj
(ns get-started.level-order-traversal
(:require [clojure.string :as string]))
(defn level-order [root]
(if (nil? root)
[]
(loop [nodes [root]
level-values []]
(if (empty? nodes)
level-values
(let [[current-level-nodes next-nodes]
(reduce (fn [[current-nodes next-nodes] node]
(if node
[(conj current-nodes (:val node))
(into next-nodes (remove nil? [(:left node) (:right node)]))]
[current-nodes next-nodes]))
[[] []]
nodes)]
(recur next-nodes (conj level-values current-level-nodes)))))))
(defn print-level-order [tree]
(let [levels (level-order tree)]
(doseq [level levels]
(println (string/join " " level)))))
(def tree
{:val 1,
:left {:val 2, :left {:val 4}}
:right {:val 3, :left {:val 5}, :right {:val 6}}})
(print-level-order tree) ; 1
; 2 3
; 4 5 6
@potetm
Copy link

potetm commented Jun 20, 2025

(copying here from twitter for ease for you)

  (defn level-order
    ([root]
     (level-order [root] []))
    ([level ret]
     (if (empty? level)
       ret
       (recur (into []
                    (comp (mapcat (juxt :left :right))
                          (filter some?))
                    level)
              (conj ret
                    (into []
                          (map :val)
                          level))))))


  (defn print-level-order [levels]
    (doseq [level levels]
      (println (clojure.string/join " " level))))

so a few concrete notes:

print-level-order: having it take the data that you want printed (as opposed to doing the transformation itself) allows it to not care how its data was generated. it just prints a list of lists.

there's an argument that reduce only does one pass on the collection, but that's probably not worth the additional complexity of tracking return values through the traversal.

into takes an xform arg, so you can (into [] (remove nil?) coll) instead of (into [] (remove nil? coll)). in theory the former is more efficient.

great work on the whole! that exercise was a little harder than I expected it to be and you handled it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment