clojure - create binary tree from input

Question

I am trying to solve this problem where you need to create a binary tree that looks like this:

              1
             / \
            2   3
           /    /
          4    5
         /    /
        /    /\
       /    /  \
       6   7    8
        \      / \
         \    /   \
          9  10   11

From this input where -1 represents a null node

[2 4][4 -1][5 -1][6 -1][7 8][-1 -9][-1 -1][10 11][-1 -1]

I am struggling being able to create the tree from this input

So far my code looks like this:

    (ns scratch.core
      (require [clojure.string :as str :only (split-lines join split)]))

    (defn numberify [str]
      (vec (map read-string (str/split str #" "))))

    (defrecord TreeNode [val left right])

    (defn tree-map [idx itm]
      (let [side (if (= 0 idx) :left :right)]
        {:val itm :side side :index idx}))

    (defn build-tree
      [node xs]
      (let [process-branch (fn process-branch [[counter t'] l]
                             (if-not (= (:val l) -1)
                               (let [next-branch (nth xs counter)]
                                 (prn "=============")
                                 (prn l)
                                 (prn counter)
                                 (prn next-branch)
                                 (prn "=============")
                                 [(inc counter) t'])
                               [counter t']))
            mark-branch (fn mark-branch [x]
                          (map-indexed tree-map x))
            [counter tree] (reduce (fn [[counter tree] x]
                                     (reduce process-branch
                                             [counter tree]
                                             (mark-branch x)))
                                   [1 node] xs)]
        tree))

(let [input "11\n2 3\n4 -1\n5 -1\n6 -1\n7 8\n-1 9\n-1 -1\n10 11\n-1 -1\n-1 -1\n-1 -1"
      lines (str/split-lines input)
      tl (read-string (first lines))
      tree-lines (map numberify (drop 1 (take (inc tl) lines)))
      tree (build-tree (TreeNode. 1 nil nil) tree-lines)])

At the moment the above code will print out this:

"============="
{:val 2, :side :left, :index 0}
1
[4 -1]
"============="
"============="
{:val 3, :side :right, :index 1}
2
[5 -1]
"============="
"============="
{:val 4, :side :left, :index 0}
3
[6 -1]
"============="
;; etc.

So I have the correct bits to make up the tree, for example the node 2 create branches from [4 -1] but what I am struggling with is how to add them to the tree without making the tree mutable.

Answer 1

Here is what I did to create the tree. It uses recursion without loop so it will blow up the stack if you give it a bunch of lines. If needed I could probably implement it with loop.

sample.txt is a file with the full input (ie the first line is the number of nodes) sitting in the resource directory.

(defn read-input [f]
  (let [[n-str & node-str] (-> (slurp f)
                               clojure.string/split-lines)
        n (Integer/parseInt n-str)]
    (->> (map vector (range 1 n) node-str)
         (map (fn [[k v]]
                (->> (clojure.string/split v #" ")
                     (mapv #(Integer/parseInt %))
                     (vector k))))
         (into {}))))

(defrecord TreeNode [val left right])

(defn make-tree [i m]
  (when-let [[l r] (get m i)]
    (->TreeNode i (make-tree l m) (make-tree r m))))

(->> (clojure-scratch.core/read-input (clojure.java.io/resource "sample.txt"))
     (clojure-scratch.core/make-tree 1))

=> #clojure_scratch.core.TreeNode{:val 1, :left #clojure_scratch.core.TreeNode{:val 2, :left #clojure_scratch.core.TreeNode{:val 4, :left #clojure_scratch.core.TreeNode{:val 6, :left nil, :right #clojure_scratch.core.TreeNode{:val 9, :left nil, :right nil}}, :right nil}, :right nil}, :right #clojure_scratch.core.TreeNode{:val 3, :left #clojure_scratch.core.TreeNode{:val 5, :left #clojure_scratch.core.TreeNode{:val 7, :left nil, :right nil}, :right #clojure_scratch.core.TreeNode{:val 8, :left #clojure_scratch.core.TreeNode{:val 10, :left nil, :right nil}, :right nil}}, :right nil}}