Question: I've been thinking for a while how I would go about implementing a doubly-linked tree or list in Scala just using immutable case classes. For most "update" operations, I've been using the copy-and-update method. For example, when setting the children of a parent, i say

```
parent = parent.copy(child=child)

```

or when setting the parent of a child, I say

```
child = child.copy(parent=parent)

```

I realize that if i set the parent to contain a child, and then create&update a new child to contain the parent, the parent would contain a reference to the old child. Similarly, if i tried to do it the other way round, the child would contain a reference to the old parent.

I want my tree to be doubly linked so I can crawl both ways: downwards from the root to his children, or upwards from a leaf to his parents. Is it possible to "simultaneously" link the parent and child nodes in this manner, to give me the circular reference I can then crawl bi-directionally?

I could easily do this using mutable data, but in my case the doubly-linked tree will exist for a long time after creation, and I want to keep it immutable if at all possible.

Answer: 
I created a blog post that describes one possible solution to your problem. 
<http://akikhtenko.github.io/blog/2013/12/15/immutable-double-linked-tree-construction-in-scala/>
It tackles trees as an example but it shouldn't be a problem to apply the idea to other data types.
Immutability in scala means that after we are finished constructing an object it should not change. During the object construction it is is actually mutable. The solution is to pass a piece of code to the constructor of the
object that calculates the required values before the fields become immutable.

```
{
  // Create a with the creation of b as a parameter.
  val a=new A( (uncomplete:A)=>new B(uncomplete) )
}

class A( bFactory:A=>B){
  //Call the bFactory then assign the result to b.
  val b=bFactory(this);
}

class B(val a:A){
}

```

Since the question talks about trees I will also include the generation of a basic tree using the same technique.

```
 class MakeTree {
  val tree = new Node(None, createSubTree _, createSubTree _);

  def createSubTree(parent: Node): Option[Node] = {
    if (parent.depth < 3)
      Some(new Node(None, createSubNode _, createSubNode _))
    else
      None
  }
}

class Node(val parent: Option[Node], leftFactory: (Node) => Option[Node], rightFactory: (Node) => Option[Node]) {
  val left = leftFactory(this);
  val right = rightFactory(this);

  def depth(): Int = parent.map(_.depth + 1).getOrElse(0);
}

```

Doing the construction like this leaves a pure immutable structure without the added overhead of accessing lazy values.