How to build an n-ary tree having same structure as another created one?

Question

I am trying to build this n-ary tree having the same structure as an already build one (when creating the new tree to be returned i would like to add the child nodes in the same positions as in the already built one , the built tree is created as follows :

        Node A = new Node("","A");
        Node B = new Node("","B");
        Node C = new Node("","C");
            ...


        Node root = A;
        root.children.add(B);
        root.children.add(C);
        root.children.add(D);

        root.children.get(1).children.add(G);
        root.children.get(1).children.get(0).children.add(K);
              ...

The Node Class is like the following :

public class Node {

    public String id;
    public ArrayList<ArrayList<String>> data;
    public Vector<Node> children = new Vector<>();

    public void setId(String id) {
        this.id = id;
    }

    public void setData(ArrayList<ArrayList<String>> data) {
        this.data = data;
    }


    public void setChildren(Vector<Node> children) {
        this.children = children;
    }

    public Node(ArrayList<ArrayList<String>> data, String id) {
        this.data = data;
        this.id = id;
    }
    public Node(ArrayList<ArrayList<String>> data,String id,Vector<Node> children) {
        this.data = data;
        this.id = id;
        this.children = children;
    }

    public Node find_parentNode(String childId) {
        if (this == null)
            return null;

        Queue<Node> queue = new LinkedList<>();
        // we add start node
        queue.add(this);

        // iterate while queue not empty
        while (!queue.isEmpty()) {
            // dequeue and print data
            Node next = queue.remove();
            

            for (Node child : next.children) {
              if (child.id == childId)
                return next;
                queue.add(child);
            }
        }
        return null;
    }

And finally the main code is the following :

       // Create rootOut (the root node to be returned)
       Node rootOut = new Node(node.data,node.id,node.children);

       queue.add(node);


        // iterate while queue not empty
        while(!queue.isEmpty()){
            // dequeue
            Node next = queue.remove();
            // we add children nodes if not null after setting an increment var for the children positions
            int j =0 ;
            for (Node child : next.children) {
                
                // Update children of rootOut (the output Tree)
                Node currentNode = rootOut.find_parentNode(child.id);

                currentNode.children.get(j).setChildren(child.children);
                currentNode.children.get(j).setData(child.data);
                currentNode.children.get(j).setId(child.id);
                j++;
                queue.add(child);
            }
        }

Basically in the main code, Instead of creating a new tree i override the values of the nodes of the built tree after having copying the old built tree into a new one (through root node rootOut), Is it a good approach ? otherwise how to create a brand new tree with the same structure (nodes positions) as the built tree ?

Thanks.

Answer 1

To duplicate the structure of an existing tree it's enough to do a depth first traversal, copying each node and adding each children in the same traversal order.

You don't need to find the parent node, that is an expensive search, since the node will be added to the right parent in the previous call of the method.

I cannot test your code, since something is missing (e.g. what is QueryNode?), but it appears to copy only the root node, without actually copying the tree structure.

So this method will recursively duplicate the tree, the only shared resources between the new and the old tree are the data ArraList, where only the reference is copied.

public static Node cloneNode(Node root) {
    Node copy=new Node(root.data, root.id);
    for (Node c: root.children) {
        copy.children.add(cloneNode(c)));
    }
    return copy;
}

As answer to your last comments, a deep copy of the data is not usual, but if you really want it just replace the first line of the method with these:

ArrayList<ArrayList<String>> copyData=new ArrayList<>();
for (ArrayList<String> l: root.data) {
    copyData.add(new ArrayList<String>(l));
}
Node copy=new Node(copyData, root.id);

Some unrelated remarks:

1. Do not use Vector, use ArrayList instead
2. In method signature and variable declaration better use the List interface insted of the concrete ArrayList class (e.g. data should be declared as List<List>)