The strategy is to decompose a complex task into a sequence of simpler tasks. The complex task is to transform a tree: we are given a tree with root r, and some designated node n. The goal is to rewrite the tree representation so that n is the new root. The further n is from r, the more complex the task. It turns out that the task is fairly simple if n is an immediate descendant of r. So the strategy is this. Find the path (sequence of nodes) from r to n, say it is [r a b c n]. We first rewrite the tree so a is the root. Then rewrite that tree so b is the root, etc. It’s that simple.
In the code I will refer to labels rather than nodes. I think of the trees this way. We have a set L of labels. Trees are constructed by induction, as follows.
- For any element x in L, [x] is a tree.
- Any vector whose first element is a label and remaining elements are trees is itself a tree.
We consider only trees wherein all labels are distinct, otherwise the problem has no unique solution. Here’s the code.
(defn get-label [x] (when (sequential? x) (first x))) (defn path-to ;;The path from the root of the tree to the label. ([label tree] (path-to  label tree)) ([path label tree] (let [lbl (get-label tree) path (conj path lbl)] (if (= label lbl) path (mapcat (partial path-to path label) (rest tree)))))) (defn lift-local ;;Rewrite the tree so that label is the root. Here label is required to belong to a subtree immediately descended from the root." [tree label] (let [match #(= label (get-label %)) subtree (first (filter match tree)) but-subtree (remove match tree)] ;; append but-subtree to subtree (concat subtree (list but-subtree)))) (defn lift ;;Rewrite the tree so that label is the root. [label tree] (reduce lift-local tree (rest (path-to label tree))))
Final thoughts: I inductively defined trees in terms of vectors, but the code does not depend on vector specific operations, and should work with trees represented by either vectors or lists. For a very different take on this problem, see Meikel Brandmeyer’s solution using logic programming.