Leetcode 1490. Clone N-ary Tree

Explanation

This problem asks us to create a deep copy of a given N-ary tree. A deep copy of an object is a copy that contains all the components of the original object, and changes to the original object do not affect the copied object. This means we need to create a new copy of each node in the original tree.

The structure of the N-ary tree is as follows:

1
2
3class Node {
4    public int val;
5    public List<Node> children;
6}

Each node contains a value (int) and a list of its children.

We can solve this problem by using Depth-first search (DFS) algorithm. Using DFS, we visit each node only once.

When we traverse the original tree, for each node, we create a new node with the same value and use DFS to copy all its children. In this way, a new N-ary tree which is the exact copy of the original tree will be created.

Algorithm walkthrough

Let's take the following N-ary tree as an example:

1
2
3    1
4   / \
5  3   2
6 /|
75  6

And its representation in level order traversal: root = [1,null,3,2,null,5,6]

  1. We will start from the root, create a new node with the same value as root.
  2. As root has children (3 and 2), We recursively call cloneTree(child) to copy the child nodes.
  3. For child 3, a new node 3 is created.
  4. As 3 has children (5 and 6), we recursively call cloneTree(child) for each of these.
  5. For child 5 and 6, new nodes 5 and 6 are generated.
  6. Now we move back to root and go to child 2, a new node 2 is created.
  7. As 2 has no children, no further action required.
  8. Finally, we return the new root of the cloned tree.

The output will be [1,null,3,2,null,5,6], the exact same representation of the input N-ary tree.

Python solution

1
2python
3class Solution:
4    def cloneTree(self, root: 'Node') -> 'Node':
5        # Check if root is not null
6        if root is None:
7            return None
8        
9        # create a new node with the same value as root
10        newNode = Node(root.val, [])
11        
12        #use dfs to copy all the children
13        for child in root.children:
14            newNode.children.append(self.cloneTree(child))
15
16        return newNode   

Java solution

1
2java
3class Solution {
4    public Node cloneTree(Node root) {
5        if (root == null)
6            return null;
7        
8        Node newNode = new Node(root.val, new ArrayList<>());
9        
10        for (Node child : root.children)
11            newNode.children.add(cloneTree(child));
12        
13        return newNode;
14    }
15}

Javascript solution

1
2javascript
3var cloneTree = function(root) {
4    if (!root) 
5        return null;
6    let node = new Node(root.val, []);
7    for (let child of root.children)
8        node.children.push(cloneTree(child));
9    return node;
10};

C++ solution

1
2cpp
3class Solution {
4public:
5    Node* cloneTree(Node* root) {
6        if (root == nullptr) 
7            return nullptr;
8        Node* new_node = new Node(root->val, {});
9        for (Node* child: root->children) 
10            new_node->children.push_back(cloneTree(child));
11        return new_node;
12    }
13};

C# solution

1
2csharp
3public class Solution {
4    public Node CloneTree(Node root) {
5        if (root == null) 
6            return null;
7        Node newNode = new Node(root.val, new List<Node>());
8        foreach (Node child in root.children)
9            newNode.children.Add(CloneTree(child));
10        return newNode;
11    }
12}

Remember that creating a deep copy of an object involves creating copies of all its components, not just the object itself. This is the reason we created a new node for each child and not just for the root.

Remember to utilize a DFS traversal method to be able to reach each node and create a new one with the same value and children.

And lastly, don't forget the base case of your DFS traversal - if root is null, return null. This will end the recursion, copy the entire subtree and avoid unnecessary null reference errors. ## Complexity analysis

For all the solutions above:

  • Time Complexity: O(N), where N is the number of nodes in the tree. Since we are doing a DFS traversal on the tree, and creating a copy of each node, we visit each node exactly once.

  • Space Complexity: O(D), where D is the maximum depth of the tree. This space is utilized by the implicit function call stack while doing the recursion for DFS.

By using a simple DFS algorithm, we are able to solve the problem of creating a deep copy of an N-ary tree. Even though copying a tree might seem like a daunting task initially, understanding the structure of the tree and the properties of its components helps simplify the complexity. Also, knowing to use an established algorithm (like DFS or BFS) is often the key to solve these types of problems.

Key points

  • Understand how the tree structure is built and how its components interact.
  • Know how to traverse the tree. Here, depth-first search (DFS) is used, but in other scenarios maybe breadth-first search (BFS) is more suitable.
  • When a deep copy is required, a new copy of all components in the original object has to be created.
  • Base case in recursion is really important. Never forget to declare it so as to end recursion after reaching termination condition.

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫