Clone N-ary Tree

LeetCode 1490: Clone N-ary Tree Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes Depth-First Search (DFS) to traverse the original tree, creating a new node instance for every visited node and recursively populating its children list.

The LeetCode 1490 problem asks us to create a deep copy of an N-ary tree. Unlike a binary tree where nodes have at most two children, an N-ary tree node can have any number of children stored in a list. A "deep copy" means we must create entirely new node objects for the entire structure; simply copying references to the existing nodes is insufficient. The structure of the new tree must exactly mirror the original.

This is a fundamental problem for understanding Clone N-ary Tree logic, often serving as a precursor to more complex graph cloning questions found in technical interviews.

Brute Force Approach for Clone N-ary Tree

A common naive approach when attempting to clone a data structure is to perform a Shallow Copy. In this approach, one might create a new root node but simply copy the list of children references from the original node to the new node without instantiating new child objects.

Naive Shallow Copy Logic

1# Pseudo-code for Shallow Copy (Incorrect)
2def cloneTree(root):
3    if root is None: return None
4    newNode = Node(root.val)
5    # The mistake: Copying the reference to the list, or references to nodes
6    newNode.children = root.children 
7    return newNode

Analysis

• Time Complexity: $O(1)$ (ignoring the list copy cost) or $O(C)$ where $C$ is the number of immediate children.
• Why it fails: This approach violates the definition of a "deep copy." The newNode has its own memory address, but its children list points to the original child nodes. If you modify a child in the cloned tree, the original tree is also modified. This fails the problem constraints which require a completely independent structure.

Algorithm Strategy: Graph Traversal Patterns (DFS)

We will implement a Depth-First Search (DFS) strategy. Since this is a tree (guaranteed no cycles), we do not strictly need a hash map to track visited nodes (which is required for general Graph Cloning), though adding one would make the solution compatible with general graphs containing cycles.

1. Base Case: If the input root is null, return null. This handles empty trees and the end of branches.
2. Instantiation: Create a new node new_node using the value from the current node.
3. Recursive Traversal: Iterate through the children list of the current node.
4. Linking: For each child, call the clone function recursively. The result of this call (a pointer/reference to the cloned child) is appended to new_node.children.
5. Return: Return new_node to the caller.

This approach effectively performs a Pre-order traversal logic (create node) combined with Post-order linking (attach children).

Execution Flow

1. Start: Call cloneTree(original_root).
2. Check Null: If original_root is null, return null immediately.
3. Create Root: Instantiate clone_root with original_root.val. Initialize an empty list for clone_root.children.
4. Process Children:
   • The algorithm loops through original_root.children.
   • Child 1: Call cloneTree(child_1).
     • Inside this call, copy_child_1 is created.
     • Recursion continues deeper until a leaf is hit.
     • The leaf returns its clone.
     • copy_child_1 attaches the cloned leaf to its children list.
     • copy_child_1 is returned.
   • Attach: clone_root adds copy_child_1 to its children list.
   • Child 2: Repeat the process.
5. Completion: Once all children are processed and attached, clone_root is fully constructed.
6. Output: Return clone_root.

Proof of Correctness

The correctness relies on structural induction.

• Base Case: For an empty tree (null), the algorithm returns null, which is correct. For a leaf node (no children), it creates a new node with the correct value and an empty children list, which is a correct deep copy.
• Inductive Step: Assume the algorithm correctly clones all subtrees of height $k$. For a tree of height $k+1$, the root is created, and for every child (which roots a subtree of height $\le k$), the recursive call returns a correct deep copy. Since the root collects these correct copies into its own list, the tree of height $k+1$ is correctly cloned.

Pattern Reuse Notes

The Graph - Deep Copy / Cloning subpattern is versatile. The logic used here—traversing structure and instantiating new objects—applies directly to:

• LeetCode 133: Clone Graph (Requires a hash map to handle cycles).
• LeetCode 138: Copy List with Random Pointer (Requires handling the "random" pointer, often using a map or interleaving nodes).
• LeetCode 1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance (Uses general graph traversal patterns).

Reference Implementation

C++ Solution for LeetCode 1490

1/*
2// Definition for a Node.
3class Node {
4public:
5    int val;
6    vector<Node*> children;
7
8    Node() {}
9
10    Node(int _val) {
11        val = _val;
12    }
13
14    Node(int _val, vector<Node*> _children) {
15        val = _val;
16        children = _children;
17    }
18};
19*/
20
21class Solution {
22public:
23    Node* cloneTree(Node* root) {
24        // Base case: if the tree is empty
25        if (root == nullptr) {
26            return nullptr;
27        }
28        
29        // Create the new node with the current node's value
30        Node* newNode = new Node(root->val);
31        
32        // Recursively clone all children
33        for (Node* child : root->children) {
34            newNode->children.push_back(cloneTree(child));
35        }
36        
37        return newNode;
38    }
39};

Java Solution for LeetCode 1490

1/*
2// Definition for a Node.
3class Node {
4    public int val;
5    public List<Node> children;
6
7    public Node() {
8        children = new ArrayList<Node>();
9    }
10
11    public Node(int _val) {
12        val = _val;
13        children = new ArrayList<Node>();
14    }
15
16    public Node(int _val, ArrayList<Node> _children) {
17        val = _val;
18        children = _children;
19    }
20};
21*/
22
23class Solution {
24    public Node cloneTree(Node root) {
25        // Base case: Handle null input
26        if (root == null) {
27            return null;
28        }
29        
30        // Create a new node instance
31        Node newNode = new Node(root.val);
32        
33        // Iterate over the original children and clone them recursively
34        for (Node child : root.children) {
35            newNode.children.add(cloneTree(child));
36        }
37        
38        return newNode;
39    }
40}

Python Solution for LeetCode 1490

1"""
2# Definition for a Node.
3class Node:
4    def __init__(self, val=None, children=None):
5        self.val = val
6        self.children = children if children is not None else []
7"""
8
9class Solution:
10    def cloneTree(self, root: 'Node') -> 'Node':
11        # Base case: empty tree
12        if not root:
13            return None
14        
15        # Create the new node copy
16        new_node = Node(root.val)
17        
18        # Recursively clone children
19        # List comprehension creates a new list of cloned nodes
20        new_node.children = [self.cloneTree(child) for child in root.children]
21        
22        return new_node