(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