Domain 2MediumMEDIUM

Clone N-ary Tree

LeetCode problem 1490: Clone N-ary Tree (medium).

Domain: medium•Updated: 2026-09-17
#Hash Table#Tree#Depth-first Search#Breadth-first Search

Problem Breakdown

We are tasked with creating a deep copy (clone) of an N-ary tree given its root node. An N-ary tree is defined where each node contains an integer value and a list of child nodes. A “deep copy” implies that the new structure must consist entirely of distinct Node objects; we cannot simply return references to the original nodes or shallow copies of lists containing pointers to existing nodes.

Inputs:

  • root: The root node of the N-ary tree (can be None).

Outputs:

  • A new root node representing an identical structure with distinct memory addresses for all nodes and children.

Constraints & Edge Cases:

  • Empty Tree: If root is None, return None. This must not crash or create a dummy object.
  • Depth Limitation: The depth is ≤1000\le 1000. In Python, the default recursion limit is often around 1000. While this solution uses recursion which fits within typical limits for LeetCode environments (which sometimes raise it), an iterative approach would be safer in production systems to avoid RecursionError.
  • Graph Follow-up: The problem asks about graphs later. Trees are acyclic, so a simple traversal works. Graphs contain cycles; cloning them requires tracking visited nodes or maintaining a mapping between original and cloned nodes to prevent infinite recursion during the clone process if we were traversing edges blindly without state management.

Intuition

A naive approach might be to serialize the tree into an array (level-order) and then reconstruct it, but that adds unnecessary O(N)O(N) space overhead for intermediate storage before reconstruction. Another “brute force” attempt is copying references directly (new_node.children = old_node.children), which fails because children would point back to original nodes rather than new ones—this violates the deep copy requirement and creates memory leaks or logical errors if we modify one tree, affecting another.

The key insight for a deep clone of an acyclic structure like a tree is that every node needs exactly one corresponding new node created during traversal. Since there are no cycles in a standard N-ary tree (unlike graphs), Depth-First Search (DFS) via recursion naturally handles this mapping perfectly:

  1. Create the current new_node.
  2. Recursively clone each child and attach them to new_node.children.

This ensures that every node is visited exactly once, creating a new object for it immediately upon entry into the function scope. For the graph follow-up mentioned in the problem description, we would need an explicit mapping (old -> new) because cycles could cause infinite recursion if not handled carefully during traversal (though standard DFS on graphs requires visited sets to avoid re-processing).

Approach

  1. Base Case: Check if root is None. If so, return None. This handles the empty tree case immediately and prevents stack overflow attempts on nulls.
  2. Recursive Step (DFS):
    • Instantiate a new Node with the same value as the current input node.
    • Iterate through each child in the original node’s children list.
    • Recursively call the clone function for every child to get their deep copies.
    • Append these cloned children into the new node’s children list.
  3. Return: Return the newly constructed root node.

This approach is clean and leverages Python’s recursion stack implicitly as our traversal mechanism, which maps directly to the tree structure definition (pre-order traversal).

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the total number of nodes in the N-ary tree. We visit every node exactly once to create its copy and link its children.
  • Space Complexity: O(H+K)O(H + K), where HH is the height of the tree (recursion stack depth) and KK represents space for new objects created. In a skewed tree, this approaches O(N)O(N). If we consider only auxiliary space excluding output size, it’s proportional to the recursion depth (O(H)O(H)).

Solution

from typing import List, Optional

# Definition for Node is assumed in LeetCode environment:
class Node:
    def __init__(self, val=None, children=[]):
        self.val = val
        self.children = children

class Solution:
    def cloneTree(self, root: 'Optional[Node]') -> 'Optional[Node]':
        # Base case: if the tree is empty or node doesn't exist, return None.
        if not root:
            return None
        
        # Create a new Node with the same value as the original.
        cloned_node = Node(root.val)
        
        # Iterate over each child of the current node and recursively clone them.
        for child in root.children:
            # Recursively call cloneTree on the child to get its deep copy,
            # then append it to the new node's children list.
            cloned_node.children.append(self.cloneTree(child))
            
        return cloned_node

# Note: In a graph context (Follow-up), we would need an explicit mapping 
# dictionary {original_node_id: cloned_node} because cycles exist in graphs,
# preventing simple recursion without visited tracking to avoid infinite loops.

Edge Cases Handled

  • Null Root: The function returns None immediately if the input root is null, satisfying the empty tree constraint.
  • Leaf Nodes: If a node has no children (empty list), the loop over root.children simply does not execute, and the new leaf node with correct value is returned correctly.
  • Deep Trees: While recursion depth matches Python’s default limit (~1000) which aligns with constraints (≤1000\le 1000), this solution assumes standard LeetCode environment limits where stack overflow isn’t triggered by valid inputs within spec. In production, an iterative BFS/DFS approach would be preferred to avoid RecursionError.
  • Memory Isolation: By creating a fresh Node instance for every recursive call and appending new children lists (via the recursion result), we ensure no reference sharing exists between original and cloned trees.