CODEWITHSUNDEEP
algorithmdata-structuresgraphtreebinary-tree
Veeresh Devireddy
Veeresh Devireddy

Reputation: 1145

How To Copy A Full Non-Binary Tree Including Loops

Please share me your thoughts and any solution to this problem of copying the full non-binary tree, and it may include loops as well in which some of the children are connected to other parent nodes.

Example:
Here, "A" is the root or parent, and its children are "B" and "C" as usual, and at the end, child "G" is connected back to its grand-parent level "B", and similarly the "I" is connected to its immediate parent "C", so these are like a loops, and this also needs to be copied in the new tree as is. So, here we need additional logic to identify the loops while copying the children nodes, and not getting into an infinite loop, and eventually return the copy of the whole tree.

A
 - B
   - D
   - E
     - F
     - G --> B
 - C
   - I --> C
   - K

This class or node structure can be like this:

public class Node{
  private String value;
  private List<Node> childrens;

  public Node copyTree(Node root) {
    ...
    //return
  }
}

Thanks for our help.

Upvotes: 1

Views: 462

Answers (1)

Ted Hopp
Ted Hopp

Reputation: 234797

I think the most direct way of doing this is to keep a map from nodes that have been copied to their copies. Then just check against the map before making a new copy of a node. Something like this (untested) should work:

public static Node copyTree(Node root) {
    return copyTree(root, new HashMap<>());
}

private static Node copyTree(Node root, Map<Node, Node> images) {
    Node copy = images.get(root);
    if (copy == null) {
        copy = new Node();

        // register the copy before recursing on children
        images.put(root, copy);

        // now fill in the copy
        copy.value = root.value;
        copy.children = new ArrayList<>();
        for (Node child : root.children) {
            copy.children.add(copyTree(child, images);
        }
    }
    return copy;
}

Upvotes: 2

Related Questions