Iterative copying (cloning) of a N-ary tree

Viewed 260

How to clone/copy N-ary tree iteratively, without recursion? Just need to rewrite cloneRecursive function iteratively:

import java.util.ArrayDeque

sealed class Row {

    abstract val name: String

    data class Section(override val name: String, val rows: List<Row>) : Row()

    data class Field(override val name: String, val data: String) : Row()
}

fun main() {
    val root = Row.Section(
        "root", listOf(
            Row.Section(
                "section 1", listOf(
                    Row.Section(
                        "section 1.1", listOf(
                            Row.Field("field 1.1.1", "1.1.1 - 1"),
                            Row.Field("field 1.1.2", "1.1.2 - 1")
                        )
                    ),
                    Row.Field("field 1.2", "1.2 - 1")
                )
            ),
            Row.Field("field 2", "2 - 1"),
            Row.Field("field 3", "3 - 1"),
            Row.Section(
                "section 4", listOf(
                    Row.Field("field 4.1", "4.1 - 1"),
                    Row.Field("field 4.2", "4.2 - 1"),
                    Row.Section(
                        "section 4.3", listOf(
                            Row.Field("field 4.3.1", "4.3.1 - 1"),
                            Row.Field("field 4.3.2", "4.3.2 - 1")
                        )
                    )
                )
            )
        )
    )

    println(root)
    println(recursiveClone(root))
    println(root == recursiveClone(root))
}

fun recursiveClone(root: Row): Row {
    return when (root) {
        is Row.Section -> {
            val rows = root.rows.map { row ->
                recursiveClone(row)
            }
            Row.Section(root.name, rows)
        }
        is Row.Field -> {
            Row.Field(root.name, root.data)
        }
    }
}
1 Answers

One approach you could try is creating a couple of stacks. The only difference from a normal iterative tree traversal using a single stack and loop is a second stack that keeps references to parents so that children can be linked. Whenever a node is visited, pop the parent stack and add the current node to the parent's child list. Afterwards, when pushing children for the current node to extend the origin stack, push a reference to the current node onto the parent stack for each child. The two stacks will always be the same size.

This simulates the ease of building child trees using recursion and passing their clones back to the parent call to populate its children list.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

class Main {
    public static Row clone(Row root) {
        if (root == null) return null;

        var originStack = new Stack<Row>();
        var parentStack = new Stack<Section>();
        originStack.push(root);
        parentStack.push(null);
        Row result = null;

        while (!originStack.isEmpty()) {
            Row curr = originStack.pop();
            Section parent = parentStack.pop();
            Row clone;

            if (curr instanceof Section) {
                clone = new Section(curr.name, new ArrayList<Row>());
                var sec = (Section)curr;

                for (int i = sec.children.size() - 1; i >= 0; i--) {
                    originStack.push(sec.children.get(i));
                    parentStack.push((Section)clone);
                }
            }
            else {
                clone = new Field(curr.name, ((Field)curr).data);
            }

            if (parent == null) {
                result = clone;
            }
            else {
                parent.children.add(clone);
            }
        }

        return result;
    }

    public static void print(Row root) {
        if (root != null) print(root, 0);
    }

    public static void print(Row root, int indent) {        
        for (int i = 0; i < indent; i++) {
            System.out.print(" ");
        }

        System.out.print(root.name);

        if (root instanceof Section) {
            System.out.println();

            for (Row child : ((Section)root).children) {
                print(child, indent + 2);
            }
        }
        else {
            System.out.println(" [" + ((Field)root).data + "]");
        }
    }

    public static void main(String[] args) {
        var root = new Section(
            "a", new ArrayList<>(Arrays.asList(
                new Section(
                    "b", new ArrayList<>(Arrays.asList(
                        new Section(
                            "c", new ArrayList<>(Arrays.asList(
                                new Field("d", "1")
                            ))
                        ),
                        new Section(
                            "e", new ArrayList<>(Arrays.asList(
                                new Field("f", "2"),
                                new Section(
                                    "g", new ArrayList<>(Arrays.asList(
                                        new Field("h", "3"),
                                        new Field("i", "4"),
                                        new Field("j", "5") 
                                    ))
                                )
                            ))
                        )
                    ))
                ),
                new Section(                    
                    "k", new ArrayList<>(Arrays.asList(
                        new Section(
                            "l", new ArrayList<>()
                        ),
                        new Field("m", "6"),
                        new Field("n", "7"),
                        new Section(
                            "o", new ArrayList<>(Arrays.asList(
                                new Field("p", "8")
                            ))
                        )
                    ))
                )
            ))
        );
        var clone = clone(root);
        ((Section)(((Section)clone).children.get(0)))
            .children.add(new Field("a new field", "42"));
        print(root);
        System.out.println("------------");
        print(clone);
        System.out.println("root is the same object as the clone: " + (root == clone));
    }
}

abstract class Row {
    String name;
}

final class Section extends Row {
    ArrayList<Row> children;

    public Section(String name, ArrayList<Row> children) {
        this.name = name;
        this.children = children;
    }
}

final class Field extends Row {
    String data;

    public Field(String name, String data) {
        this.name = name;
        this.data = data;
    }
}

Output:

a
  b
    c
      d [1]
    e
      f [2]
      g
        h [3]
        i [4]
        j [5]
  k
    l
    m [6]
    n [7]
    o
      p [8]
------------
a
  b
    c
      d [1]
    e
      f [2]
      g
        h [3]
        i [4]
        j [5]
    a new field [42]
  k
    l
    m [6]
    n [7]
    o
      p [8]
root is the same object as the clone: false
Related