clojure - create binary tree from input

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.