Cloning Tree Structure - One Node Type to Another

user_19186780 0
Viewed 39

I'm looking to convert a tree using one type to node to another type, and I've been stuck on this for longer than I wish to admit.

So lets say the original tree looks like this:

Node: String, Children (Node)

I want to clone this tree but instead have:

Node2: String, Children (Node2), String

I'm stuck on how I can recursively go through the initial tree and then clone all the nodes to be using Node2 parameters.

Any help would be greatly appreciated!

Update: Used the answer provided by @tgdavies and ended up with:

private fun cloneTree(
    nodeA: Node_1,
    createB: BiFunction<Node_1, List<Node_2>?, Node_2>
): Node_2 {
    val children: List<Node_2> = nodeA.children
        .stream()
        .map { anA -> cloneTree(anA, createB) }
        .collect(Collectors.toList())
    return createB.apply(nodeA, children)
}
kotlin tree data-structures clone java
1 Answers

Just create a new root Node2 using a list of children we've already converted to Node2 and the data from the Node root node.

Here's one approach:

import java.util.List;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.stream.Collectors;

import static java.util.List.of;

class Node {
    final String data;
    final List<Node> children;

    Node(String data, List<Node> children) {
        this.data = data;
        this.children = children;
    }
}

class Node2 {
    final String data;
    final String data2;
    final List<Node2> children;

    Node2(String data, String data2, List<Node2> children) {
        this.data = data;
        this.data2 = data2;
        this.children = children;
    }
}


public class TreeClone {

    static <A,B> B cloneTree(A a, BiFunction<A,List<B>,B> createB, Function<A,List<A>> extractAChildren) {
        List<B> children = extractAChildren.apply(a)
                .stream()
                .map(anA -> cloneTree(anA, createB, extractAChildren))
                .collect(Collectors.toList());
        return createB.apply(a, children);
    }

    public static void main(String[] args) {
        Node n = new Node("root", 
                of(new Node("child1", 
                        of(new Node("gchild", of()))), 
                        new Node("child2", of())
                )
        );
        Node2 n2 = cloneTree(n,
                (from, children) -> new Node2(from.data, from.data.toUpperCase(), children),
                node -> node.children
        );
    }
}
user_110020
Related