1490. Clone N-ary Tree

MediumTreeDepth-First SearchBreadth-First SearchHash Table

Problem Description

In this problem, we are given the root of an N-ary tree and asked to create a deep copy of it. A deep copy means that we should create an entirely new tree, where each node is a new instance with the same values as the corresponding nodes in the original tree. In other words, modifying the new tree should not affect the original tree.

An N-ary tree is a tree in which a node can have zero or more children. This differs from a binary tree where each node has at most two children. Each node in an N-ary tree holds a value and a list of nodes that represent its children.

The tree is represented using a custom Node class. The Node class consists of two attributes:

val: an integer representing the value of the node.
children: a list of child nodes.

We are to perform the deep copy without altering the structure or values of the original tree.

Flowchart Walkthrough

Let's analyze the problem of cloning an N-ary tree using the Flowchart. Here's a step-by-step approach to determine the suitable algorithm:

Is it a graph?

Yes: An N-ary tree is a form of graph where each node can have multiple children.

Is it a tree?

Yes: The structure specifically defined is an N-ary tree.

Is the problem related to directed acyclic graphs (DAGs)?

No: Though technically a tree is a type of acyclic graph, the problem isn't about handling general directed acyclic graph issues; rather, it's about directly working within a tree structure.

Conclusion: The flowchart reveals that for tree-related problems where we are not dealing with DAG-specific concepts or shortest paths, the suggested approach is to use DFS for an effective and straightforward tree traversal. DFS is particularly suited here as we need to traverse each node in the tree to clone it. Hence, Depth-First Search (DFS) is the most appropriate pattern to apply for cloning an N-ary tree efficiently.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The intuition behind solving the deep copy problem for an N-ary tree lies in understanding tree traversal and the idea of creating new nodes as we traverse. Since we need to create a new structure that is identical to the original tree, we will use a Depth-First Search (DFS) traversal. DFS allows us to visit each node, starting from the root, and proceed all the way down to its children recursively before backtracking.

Here's the breakdown of the approach:

Start from the root of the tree. If the root is None, meaning the tree is empty, return None as there is nothing to copy.
For a non-empty tree, create a new root node for the cloned tree with the same value as the original root.
Recursively apply the same clone process for all the children of the root node. Create a list of cloned children by iterating through the original node's children and applying the cloning function on each of them.
Assign the list of cloned children to the new root node's children attribute.
Once the recursion ends, we will have a new root node with its entire subtree cloned.

The code snippet provided uses this recursive approach for cloning each node. The recursion naturally handles the depth-first traversal of the tree and cloning of sub-trees rooted at each node's children.

Learn more about Tree, Depth-First Search and Breadth-First Search patterns.

Solution Approach

The provided code snippet implements the deep copy of an N-ary tree using a straightforward recursive strategy, which aligns with the DFS (Depth-First Search) method indicated in the Reference Solution Approach. DFS is a fundamental algorithm used in tree traversal, where we explore as far as possible along each branch before backtracking.

Here's a walk-through of the solution approach, highlighting the algorithm, data structures, and patterns involved:

Definition of the cloneTree function:
- It takes one parameter, root, which represents the root of the N-ary tree we want to clone.
- The function is designed to return a new Node that is the root of the cloned tree.
Base Case:
- The recursion starts by checking if the root is None. If so, it returns None because an empty tree cannot be copied.
Recursive Case:
- If the root is not None, the function creates a clone of the root node's list of children:
- children = [self.cloneTree(child) for child in root.children]
  - This line iterates over each child of the current root node and applies the cloneTree function recursively, creating a deep copy of each subtree rooted at every child.
- A new Node instance is created using the original node's value, root.val, and the list of cloned children, children. This line effectively clones the current root node and its entire subtree.
Data Structure Usage:
- A list comprehension is used to succinctly clone all the children for a given node and construct a list of these cloned children.
- The Node class is central to the solution. New instances of Node are created to form the cloned tree, and they are dynamically linked together through the children attribute to mimic the structure of the original tree.
Recursion:
- The recursive call structure ensures that the DFS is executed correctly. It clones the nodes in a depth-first manner, starting at the root, down to the leaves, and then backtracking to cover all nodes.
Pattern:
- The pattern here is a typical DFS recursion pattern tailored to handle N-ary trees as opposed to binary trees.

By iteratively applying this cloning process to each node, starting from the root and moving depth-first into each branch of the tree, the algorithm successfully constructs a deep copy of the entire N-ary tree. The recursive approach, while elegant and simple, takes advantage of the call stack to keep track of the nodes yet to be visited and the children list to maintain the tree structure in the cloned tree.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a small example of an N-ary tree. Consider the following tree structure:

Here, node 1 is the root with three children 2, 3, and 4. Node 2 has two children 5 and 6. The node class for each of these would look something like this:

Node(1, [Node(2), Node(3), Node(4)])
Node(2, [Node(5), Node(6)])

Now, let's walk through the steps in our algorithm to create a deep copy of this tree:

We call cloneTree(root) where root is Node(1).
Since root is not None, we proceed to clone its children. We iterate over the children [Node(2), Node(3), Node(4)].
First, we clone Node(2). Since it has children [Node(5), Node(6)], we:
- Recursively call cloneTree on Node(5), which has no children. We create a new instance Node(5) and return it.
- Recursively call cloneTree on Node(6), also creating a new instance Node(6) and return it.
- With both Node(5) and Node(6) cloned, we create a new instance Node(2) with the cloned children and return it.
Next, Node(3) is cloned. It has no children, so we simply create a new instance of Node(3) and return it.
Finally, Node(4) is also cloned without children, resulting in a new Node(4).
Now that all children of the root have been cloned, we create a new root Node(1) with the cloned children [Node(2), Node(3), Node(4)].
The cloning process of the entire tree is complete, and we return the new root Node(1). This root points to the entirely cloned N-ary tree.

The cloned tree structure is now as follows, and modifying this new tree has no impact on the original tree:

       1 (new)
     / | \
    2  3  4 (new for each)
   / \
  5   6 (new for each)

At each step, recursive calls ensure that an entirely new node instance is created for every node in the original tree. The list comprehensions and Node class instances ensure that the tree structure is preserved in the deep copy process.

Through the intuition and the steps highlighted above, one can grasp how the depth-first recursive approach facilitates an efficient deep copy of an N-ary tree.

Solution Implementation

1class Node:
2    def __init__(self, value=None, children=None):
3        """
4        Node structure for N-ary tree with optional value and children list arguments.
5        :param value: value of the node, defaulted to None
6        :param children: list of child nodes, defaulted to empty list if None
7        """
8        self.value = value
9        self.children = [] if children is None else children
10
11
12class Solution:
13    def cloneTree(self, root: 'Node') -> 'Node':
14        """
15        Clones an N-ary tree.
16        :param root: The root node of the tree to clone.
17        :return: The root node of the cloned tree.
18        """
19        # If the root is None, return None to handle the empty tree case
20        if root is None:
21            return None
22
23        # Use list comprehension to recursively clone each subtree rooted at the children of the current node
24        cloned_children = [self.cloneTree(child) for child in root.children]
25
26        # Create a clone of the current node with the cloned children
27        cloned_node = Node(root.value, cloned_children)
28
29        return cloned_node
30

1class Solution {
2    // This method creates a deep copy of a tree with nodes having an arbitrary number of children.
3    public Node cloneTree(Node root) {
4        // If the current node is null, return null because there is nothing to clone.
5        if (root == null) {
6            return null;
7        }
8
9        // Initialize a list to hold the cloned children nodes.
10        ArrayList<Node> clonedChildren = new ArrayList<>();
11
12        // Recursively clone all the children of the current node.
13        for (Node child : root.children) {
14            clonedChildren.add(cloneTree(child));
15        }
16
17        // Create a new node with the same value as the current node and the list of cloned children.
18        return new Node(root.val, clonedChildren);
19    }
20}
21
22// Definition for a Node.
23class Node {
24    public int val; // Variable to store the node's value.
25    public List<Node> children; // List to store the node's children.
26
27    // Constructor to initialize the node with no children.
28    public Node() {
29        children = new ArrayList<Node>();
30    }
31
32    // Constructor to initialize the node with a value and no children.
33    public Node(int val) {
34        this.val = val;
35        children = new ArrayList<Node>();
36    }
37
38    // Constructor to initialize the node with a value and a list of children.
39    public Node(int val, ArrayList<Node> children) {
40        this.val = val;
41        this.children = children;
42    }
43}
44

1class Solution {
2public:
3    // This function clones an N-ary tree starting at the root node.
4    Node* cloneTree(Node* root) {
5        // If the root is nullptr, there's nothing to clone; return nullptr.
6        if (!root) {
7            return nullptr;
8        }
9
10        // Create an empty vector to hold the cloned children.
11        std::vector<Node*> clonedChildren;
12
13        // Iterate through each child of the root node.
14        for (Node* child : root->children) {
15            // Recursively clone each child and add the cloned child to the clonedChildren vector.
16            clonedChildren.push_back(cloneTree(child));
17        }
18
19        // Create and return a new node with the cloned value and cloned children.
20        return new Node(root->val, clonedChildren);
21    }
22};
23

1// Define the structure for a Node in TS, which includes a value and an array of children Nodes.
2class Node {
3    public val: number;
4    public children: Node[];
5
6    constructor(val: number, children: Node[] = []) {
7        this.val = val;
8        this.children = children;
9    }
10}
11
12// This function clones an N-ary tree starting at the root node.
13function cloneTree(root: Node | null): Node | null {
14    // If the root is null, there's nothing to clone; return null.
15    if (!root) {
16        return null;
17    }
18
19    // Create an empty array to hold the cloned children.
20    let clonedChildren: Node[] = [];
21
22    // Iterate through each child of the root node.
23    for (let child of root.children) {
24        // Recursively clone each child and add the cloned child to the clonedChildren array.
25        clonedChildren.push(cloneTree(child));
26    }
27
28    // Create and return a new Node with the cloned value and cloned children.
29    return new Node(root.val, clonedChildren);
30}
31

Time and Space Complexity

Time Complexity

The time complexity of the cloneTree function is O(N), where N is the total number of nodes in the tree. This is because the function visits each node exactly once to create its clone.

Space Complexity

The space complexity of the function is also O(N) in the worst case. This space is required for the call stack due to recursion, which could go as deep as the height of the tree in the case of a skewed tree. Additionally, space is needed to store the cloned tree, which also contains N nodes.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which of these pictures shows the visit order of a depth-first search?

I don't know