In a previous post we introduced the tree-reparenting exercise.

Tree visualization

To help understand the way we are representing trees (as lists of lists), we'll use the Rhizome library to visualize the test cases, the original tree (left) and the new tree we want (right):

(=  (tree-reparent 'a '(t (e) (a)))
   '(a (t (e))))

We will transform the tree on the left into the one on the right by "pulling" the a node up to the top:

'(t (e) (a)) -> '(a (t (e)))

All the same connections are left intact, we have simply repositioned the nodes. Here's a slightly more complex tree:

(= (tree-reparent 'd '(a (b (c) (d) (e)) (f (g) (h))))
    '(d (b (c) (e) (a (f (g) (h))))))

'(a (b (c) (d) (e)) (f (g) (h))) -> '(d (b (c) (e) (a (f (g) (h)))))

Solution

The tree above is defined here as tree1. The tree-seq function returns a lazy sequence of the nodes in a tree, via a depth-first walk.

(def tree1
  '(a
     (b (c) (d) (e))
     (f (g) (h))))

(tree-seq next rest tree1)

The call to tree-seq returns a list of lists, one for each node. Now filter out only the sublists that contain d, our new root:

(filter #(some #{'d} (flatten %))
        (tree-seq next rest tree1))

That leaves 3 lists. Construct the new tree by removing the items of the second list from the first, and appending the result to the first list:

(reduce
  (fn [a b] (concat b
                   (list (remove #{b} a))))
      '((a (b (c) (d) (e)) (f (g) (h)))
      (b (c) (d) (e))
      (d)))

We have now built all the pieces to complete the tree-reparent function.