c# deep copy of n-ary tree

Question

I have n-ry tree with node like this:

class Node
{
  public Node Parent = null;
  public List<Node> Children = new List<Node>();
  public string Name;
}

I need to do a deep copy of original tree and avoid changing of new tree when original tree is changed. I know only how to do shallow copy:

public Node Copy(Node original)
{
  Node newNode = new Node();
  newNode.Parent = original.Parent;
  newNode.Children = original.Children;
  newNode.Name = original.Name;

  return newNode;
}

In this case I copy both Nodes point to on object in memory and when original node changed a newNode will be changed to. Could anyone help me to do deep cloning?

That's because all properties aren't copied. They are just referenced in another object. — kevintjuh93, Sep 18 '15 at 08:21
Possible duplicate of http://stackoverflow.com/questions/78536/deep-cloning-objects. This is a similar question asked in a different way. — Viet Nguyen, Sep 18 '15 at 08:27
That's because all properties aren't copied. They are just referenced in another object. — kevintjuh93, Sep 18 '15 at 08:30

score 1 · Answer 1 · answered Sep 18 '15 at 08:49

You've to do it recursively. And you need a parent for the created clone.

public Node Copy(Node origin, Node parent = null)
{
    if (origin == null)
    {
        return null;
    }

    var result = new Node { Parent = parent, Name = origin.Name };
    result.Children = origin.Children != null ? origin.Children.Select(x => Copy(x, result)).ToList() : null;
    return result;
}

This will help if you only have Node and no system types.

score 0 · Answer 2 · answered Sep 18 '15 at 08:44

Do it recursivly. Note that this will set the parent of the first node to null. I.e. if you start copying from the middle of the tree, the parent node will not be maintained.

public Node Copy()
{
  Node newNode = new Node();
  newNode.Name = this.Name;

  foreach(var child in this.Children)
  {
      newChild = child.Copy();
      newChild.Parent = newNode;
      newNode.Children.Add(newChild);
  }

  return newNode;
}

c# deep copy of n-ary tree

2 Answers2