GoLang: Recursive Algorithm to Clone N-ary Tree

Given a root of an N-ary tree, return a deep copy (clone) of the tree.

Each node in the n-ary tree contains a val (int) and a list (List[Node]) of its children.

1 2 3 4

class Node {     public int val;     public List<Node> children; }

class Node {
    public int val;
    public List<Node> children;
}

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Follow up: Can your solution work for the graph problem?

n-ary-tree

Example 1:
Input: root = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]

Example 2:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

Constraints:
The depth of the n-ary tree is less than or equal to 1000.
The total number of nodes is between [0, 10^4].

Hints:
Traverse the tree, keep a hashtable with you and create a clone node for each node in the tree.
Start traversing the original tree again and connect each child pointer in the cloned tree the same way as the original tree with the help of the hashtable.

GoLang to Clone a N-ary Tree

We can recursively clone the children and the root node itself. In GoLang, we use “make” to allocate a list, and we use &struct to new an object.

As we are iterating recursively for each node in the N-nary tree, the time complexity is O(N) and space complexity is also O(N) where N is the number of the nodes in the N-nary tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
 
func cloneTree(root *Node) *Node {    
    if root == nil {
        return nil
    }
    var children = make([]*Node, 0)
    for _, c := range root.Children {
        children = append(children, cloneTree(c))
    }
    return &Node{root.Val, children}
}

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func cloneTree(root *Node) *Node {    
    if root == nil {
        return nil
    }
    var children = make([]*Node, 0)
    for _, c := range root.Children {
        children = append(children, cloneTree(c))
    }
    return &Node{root.Val, children}
}

See also: Deep Clone N-ary Tree using Hash Map + Recursive Depth First Search Algorithm

–EOF (The Ultimate Computing & Technology Blog) —