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.