Difficulty: 🟡 Medium
Topics: Hash Table, Tree, Depth-First Search, Breadth-First Search

Solution

LeetCode 1490 - Clone N-ary Tree

Problem Understanding

This problem asks us to create a deep copy of an N-ary tree. An N-ary tree is a tree where each node can have zero or more children, unlike a binary tree which limits each node to at most two children.

Each node contains two fields:

val, the integer value stored in the node
children, a list containing references to child nodes

A deep copy means the cloned tree must consist entirely of newly created nodes. None of the nodes in the copied tree can reference nodes from the original tree. However, the structure and values of the cloned tree must exactly match the original.

The input is the root node of the original N-ary tree. The expected output is the root node of a completely independent cloned tree.

For example, if the original tree contains a node with value 3 and children 5 and 6, then the cloned tree must also contain a new node with value 3 connected to new nodes with values 5 and 6. The cloned nodes must not share memory references with the original nodes.

The constraints are important:

The tree depth can be as large as 1000
The total number of nodes can be up to 10,000

These constraints tell us that the solution must be efficient. An exponential or repeated-copy approach would be far too slow. Since every node must appear in the cloned tree exactly once, an optimal solution should ideally process each node a single time.

There are several important edge cases:

The input tree may be empty, meaning root == None
A node may have zero children
The tree may be very deep, which can stress recursive solutions
The tree may be very wide, meaning nodes can contain many children

The problem guarantees that the input is a valid tree, not a graph with cycles. That simplifies the cloning process because we do not need cycle detection for this version of the problem.

Approaches

Brute Force Approach

A naive approach would attempt to reconstruct the tree level by level while repeatedly traversing parts of the original tree to rebuild child relationships. For example, we could serialize the tree into an intermediate representation and then deserialize it into a new tree.

This works because serialization preserves the structure and values of the tree. However, this introduces unnecessary overhead. We would traverse the tree multiple times, allocate extra storage for the serialized representation, and perform redundant work reconstructing nodes.

Additionally, serialization logic for N-ary trees can become cumbersome because child boundaries must be preserved correctly.

Although this approach eventually produces the correct cloned tree, it is inefficient and unnecessarily complex.

Optimal Approach

The key insight is that cloning a tree naturally matches recursive traversal.

For every node in the original tree:

Create a new node with the same value
Recursively clone each child
Attach the cloned children to the new node

This works because trees are recursive data structures. Every subtree is itself an N-ary tree. If we can correctly clone a subtree rooted at a node, then recursively cloning the entire structure becomes straightforward.

Depth-First Search is particularly well suited here because:

We visit each node exactly once
We immediately build the cloned structure while traversing
Parent-child relationships are preserved naturally through recursion

Since the input is guaranteed to be a tree without cycles, we do not need a visited set or hash map for this problem.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) to O(n²)	O(n)	Serialization and reconstruction introduce unnecessary overhead
Optimal DFS Clone	O(n)	O(h)	Visits each node exactly once, where h is tree height

Algorithm Walkthrough

Check whether the root is None.

If the tree is empty, there is nothing to clone, so return None. 2. Create a new node for the current root.

The cloned node should contain the same value as the original node. At this stage, the cloned node has an empty children list. 3. Traverse each child of the current node.

Since the children themselves are roots of smaller subtrees, recursively clone each child subtree. 4. Append cloned children to the new node.

After recursively cloning a child, add the cloned child node into the cloned parent's children list. 5. Return the cloned node.

Once all children are processed, the cloned subtree is complete. 6. The recursive calls continue until every node in the tree has been cloned.

Why it works

The algorithm works because of structural recursion on trees.

For every original node, we create exactly one corresponding cloned node. The recursive step guarantees that every child subtree is also cloned completely before being attached to the cloned parent.

Since trees contain no cycles, recursion eventually terminates at leaf nodes. The parent-child relationships are preserved exactly because cloned children are attached in the same order as the original children.

Therefore, the resulting tree is structurally identical to the original while containing entirely separate node objects.

Python Solution

"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children if children is not None else []
"""

class Solution:
    def cloneTree(self, root: 'Node') -> 'Node':
        if root is None:
            return None

        cloned_root = Node(root.val)

        for child in root.children:
            cloned_child = self.cloneTree(child)
            cloned_root.children.append(cloned_child)

        return cloned_root

The implementation begins by handling the empty tree case. If root is None, the function immediately returns None.

Next, a new node is created using the current node's value. This ensures the cloned node is completely independent from the original.

The function then iterates through every child in the original node's children list. Each child subtree is recursively cloned by calling cloneTree(child).

The returned cloned child is appended into the cloned node's children list. This preserves both the structure and ordering of children.

Finally, the fully constructed cloned node is returned upward through the recursion stack.

The implementation is concise because the recursive structure of the algorithm directly mirrors the recursive structure of the tree itself.

Go Solution

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

func cloneTree(root *Node) *Node {
	if root == nil {
		return nil
	}

	clonedRoot := &Node{
		Val:      root.Val,
		Children: []*Node{},
	}

	for _, child := range root.Children {
		clonedChild := cloneTree(child)
		clonedRoot.Children = append(clonedRoot.Children, clonedChild)
	}

	return clonedRoot
}

The Go implementation follows the same recursive structure as the Python solution.

The primary difference is explicit pointer handling. Nodes are represented as pointers using *Node, and new nodes are allocated with &Node{}.

The Children field is initialized as an empty slice to allow appending cloned child nodes safely.

Go does not have recursion depth protection like Python's recursion limit, but the problem constraint of depth at most 1000 is generally manageable.

Since Go slices dynamically resize, appending cloned children is straightforward and efficient.

Worked Examples

Example 1

Input:

root = [1,null,3,2,4,null,5,6]

Tree structure:

Step-by-step traversal

Current Node	Action	Cloned Structure
1	Create clone node 1	1
3	Clone child of 1	1 -> 3
5	Clone child of 3	1 -> 3 -> 5
6	Clone child of 3	1 -> 3 -> 6
2	Clone child of 1	1 -> 2
4	Clone child of 1	1 -> 4

Final cloned tree:

Every node in the cloned tree is newly allocated.

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]

This tree is deeper and contains multiple branching levels.

Recursive cloning flow

Node	Children
1	2, 3, 4, 5
3	6, 7
7	11
4	8
5	9, 10
9	12
10	13
13	14

The algorithm recursively clones each subtree:

Clone node 1
Clone children 2, 3, 4, 5
While cloning 3, recursively clone 6 and 7
While cloning 7, recursively clone 11
Continue recursively for all remaining subtrees

Since every subtree is cloned independently before attachment, the final structure exactly matches the original.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(h)	Recursive call stack stores at most tree height h

The time complexity is linear because the algorithm performs constant work for each node. Every node is cloned once, and every edge is traversed once.

The space complexity comes from recursion depth. In the worst case of a completely skewed tree, the recursion stack can grow to O(n). In balanced trees, the recursion depth is much smaller.

Test Cases

# Definition for testing
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

class Solution:
    def cloneTree(self, root):
        if root is None:
            return None

        cloned_root = Node(root.val)

        for child in root.children:
            cloned_root.children.append(self.cloneTree(child))

        return cloned_root

def serialize(root):
    if not root:
        return []

    result = []

    def dfs(node):
        result.append(node.val)
        for child in node.children:
            dfs(child)

    dfs(root)
    return result

solution = Solution()

# Test 1: Empty tree
assert solution.cloneTree(None) is None  # verifies empty input handling

# Test 2: Single node
root = Node(1)
cloned = solution.cloneTree(root)
assert cloned.val == 1  # verifies single node cloning
assert cloned is not root  # verifies deep copy

# Test 3: One level of children
root = Node(1, [Node(2), Node(3), Node(4)])
cloned = solution.cloneTree(root)
assert serialize(cloned) == [1, 2, 3, 4]  # verifies child cloning

# Test 4: Multi-level tree
root = Node(
    1,
    [
        Node(2),
        Node(3, [Node(5), Node(6)]),
        Node(4)
    ]
)
cloned = solution.cloneTree(root)
assert serialize(cloned) == [1, 2, 3, 5, 6, 4]  # verifies recursive subtree cloning

# Test 5: Deep tree
root = Node(1, [Node(2, [Node(3, [Node(4)])])])
cloned = solution.cloneTree(root)
assert serialize(cloned) == [1, 2, 3, 4]  # verifies deep recursion handling

# Test 6: Verify deep copy independence
root = Node(1, [Node(2)])
cloned = solution.cloneTree(root)
cloned.children[0].val = 99
assert root.children[0].val == 2  # verifies original tree is unaffected

# Test 7: Node with many children
root = Node(1, [Node(i) for i in range(2, 20)])
cloned = solution.cloneTree(root)
assert len(cloned.children) == 18  # verifies wide tree handling

Test Case Summary

Test	Why
Empty tree	Verifies correct handling of `None` input
Single node	Ensures isolated nodes clone correctly
One level of children	Validates child list cloning
Multi-level tree	Verifies recursive subtree copying
Deep tree	Tests recursion depth handling
Deep copy independence	Ensures cloned nodes are separate objects
Wide tree	Verifies many-child scenarios

Edge Cases

Empty Tree

One important edge case is when the input root is None. A naive implementation might attempt to access root.val immediately, causing a runtime error.

The implementation handles this safely by checking if root is None at the start and returning None immediately.

Leaf Nodes

Leaf nodes contain no children. Some implementations accidentally assume every node has children and may iterate incorrectly or initialize invalid references.

This solution handles leaf nodes naturally because iterating over an empty children list simply performs zero recursive calls.

Deep Trees

A highly skewed tree can create recursion depth close to 1000. Recursive solutions that accidentally recurse multiple times per child or duplicate work could become inefficient or unstable.

This implementation performs exactly one recursive call per child and maintains linear complexity. The recursion depth grows only with the actual tree depth.

Deep Copy Validation

One subtle bug occurs when developers accidentally reuse child references from the original tree instead of creating new nodes.

This implementation always allocates a brand-new Node object before recursively cloning children. As a result, the cloned tree is fully independent from the original.