Chris Houser contributed the very pretty problem 130 to 4clojure. I won’t repeat the problem statement here, just my thoughts on how to approach the problem, and my solution.

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.