Swap nodes in binary tree in clojure

Question

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

From this input where -1 represents a null node

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

Once you have done that, the problem asks you to swap nodes at a given depth.

So far I have this code that creates the tree:

(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 preprocess-input [n xs]
  (let [source (map vector (range 1 n) xs)]
    (->> source
         (map (fn [[k v]]
                {k v}))
         (into {}))))

(defn build-tree [val source]
  (when-let [[l r] (get source val)]
    (TreeNode. val (build-tree l source) (build-tree r source))))

(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\n2\n2\n4"
      lines (str/split-lines input)
      tree-length (read-string (first lines))
      tree-lines (map numberify (drop 1 (take (inc tree-length) lines)))
      tree-source (preprocess-input tree-length tree-lines)
      tree (build-tree 1 tree-source)
      swap-depths (map read-string (vec (take-last (Integer/parseInt (get lines (inc tree-length))) lines)))])

I am totally stuck with how to swap the nodes, I have tried this function:

(defn walk-tree [node curr swap-depth]
  (when node
    (let [left (:left node)
          right (:right node)
          val (:val node)]
      (if (= curr swap-depth)
        (TreeNode. val (walk-tree right (inc curr) swap-depth) (walk-tree left (inc curr) swap-depth))
    (TreeNode. val (walk-tree left (inc curr) swap-depth) (walk-tree right (inc curr) swap-depth))))))

But I think I should be going BFS rather than DFS because while I can swap a node this way, it gets swapped back when the right node is encountered.

Though I modified a bit, your example still has some inconsistencies on when, and when not, [-1 -1] appears. — Davyzhu
– Davyzhu, Commented Aug 24, 2015 at 3:32
I understand your swapping as modifying a given node by, possibly incrementing its value? This can be done even without the construction of such a tree. The number of vectors in one layer, is the number of valid (non-minus-1) nodes in last layer. Therefore, one can get all nodes of a given layer by one-time-scanning the input — Davyzhu
– Davyzhu, Commented Aug 24, 2015 at 3:36
The link to the problem got lost somehow. And theres -9 in the example input, likely a typo. And do you need to swap nodes only at the given depth or deeper as well? And I believe DFS is just fine here, I would use it. — D-side
– D-side, Commented Aug 24, 2015 at 5:08
Well, my edit got rejected. Perhaps SO only encourages edits that change ONLY formatting. I'd suggest you revise your post yourself. In addition to the -9 typo, the first element should be [2 3], the last [-1 -1] should also be remove, right? — Davyzhu
– Davyzhu, Commented Aug 24, 2015 at 6:30

Davyzhu · Accepted Answer · 2015-08-24 14:36:31Z

1

Like I've said in the comment, I'd approach this in these two ways:

Take this as a String manipulation problem. First split it into a seq of lines. Then define a function that takes m and a-seq, and eats the first m elements from the a-seq, and produces a n where n indicates the number of valid nodes in this layer and the remaining seq. Repeat this depth times and you are now at the given depth. Do whatever required. There should be other viable methods as well.
Construct a tree-like structure. But instead of simply keeping the value given at each node, the depth is also attached. Then use clojure.walk/postwalk to traverse the tree, update value when seeing nodes at the given depth.

answered Aug 24, 2015 at 14:36

Davyzhu

1,1199 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Swap nodes in binary tree in clojure

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related