1. Recursion

Intuition

Cloning an N-ary tree is a natural fit for recursion. For each node, we create a copy with the same value, then recursively clone all of its children. The recursive structure mirrors the tree structure itself, making the solution straightforward and elegant.

Algorithm

1. Base case: If the node is null, return null.
2. Create a new node with the same value as the current node.
3. For each child of the current node, recursively clone the child and add it to the new node's children list.
4. Return the newly created node.

class Solution:
    def cloneTree(self, root: 'Node') -> 'Node':

        # Base case: empty node.
        if not root:
            return root

        # First, copy the node itself.
        node_copy = Node(root.val)

        # Then, recursively clone the sub-trees.
        for child in root.children:
            node_copy.children.append(self.cloneTree(child))

        return node_copy

Time & Space Complexity

• Time complexity: $O(M)$
• Space complexity: $O(M)$

Where $M$ is the number of nodes in the input tree.

---

2. DFS with Iteration

Intuition

We can avoid recursion by using an explicit stack. We maintain pairs of (original node, cloned node) on the stack. When we pop a pair, we iterate through the original node's children, create cloned children, link them to the cloned parent, and push the new pairs onto the stack for further processing.

Algorithm

1. If root is null, return null.
2. Create the cloned root and push the pair (root, new_root) onto a stack.
3. While the stack is not empty:
   • Pop a pair (old_node, new_node).
   • For each child of old_node:
     • Create a new cloned child node.
     • Append the cloned child to new_node's children.
     • Push the pair (child, new_child) onto the stack.
4. Return the cloned root.

class Solution:
    def cloneTree(self, root: 'Node') -> 'Node':

        if not root:
            return root

        new_root = Node(root.val)
        # Starting point to kick off the DFS visits.
        stack = [(root, new_root)]

        while stack:
            old_node, new_node = stack.pop()
            for child_node in old_node.children:
                new_child_node = Node(child_node.val)

                # Make a copy for each child node.
                new_node.children.append(new_child_node)

                # Schedule a visit to copy the child nodes of each child node.
                stack.append((child_node, new_child_node))

        return new_root

Time & Space Complexity

• Time complexity: $O(M)$
• Space complexity: $O(\log_{n}{M})$

Where $M$ is the number of nodes in the input tree and $N$ is the maximum number of children that a node can have

---

3. BFS

Intuition

Instead of depth-first traversal with a stack, we can use breadth-first traversal with a queue. This processes nodes level by level. The logic is the same as the iterative DFS approach, but we use a queue instead of a stack, removing from the front instead of the back.

Algorithm

1. If root is null, return null.
2. Create the cloned root and enqueue the pair (root, new_root).
3. While the queue is not empty:
   • Dequeue a pair (old_node, new_node) from the front.
   • For each child of old_node:
     • Create a new cloned child node.
     • Append the cloned child to new_node's children.
     • Enqueue the pair (child, new_child).
4. Return the cloned root.

class Solution:
    def cloneTree(self, root: 'Node') -> 'Node':

        if not root:
            return root

        new_root = Node(root.val)
        # Starting point to kick off the BFS visits.
        queue = deque([(root, new_root)])

        while queue:
            # Get the element from the head of the queue.
            old_node, new_node = queue.popleft()

            for child_node in old_node.children:
                new_child_node = Node(child_node.val)

                # Make a copy for each child node.
                new_node.children.append(new_child_node)

                # Schedule a visit to copy the child nodes of each child node.
                queue.append((child_node, new_child_node))

        return new_root

Time & Space Complexity

• Time complexity: $O(M)$
• Space complexity: $O(M)$

Where $M$ is the number of nodes in the input tree.

---

Common Pitfalls

Returning the Original Node Instead of a Clone

A common mistake is returning the original node in the base case or forgetting to create a new node, which means the "clone" still shares references with the original tree.

# Wrong: Returns original node
if not root:
    return root  # Fine for null, but ensure you create NEW nodes otherwise
# Must use: node_copy = Node(root.val)

Shallow Copying the Children List

Directly assigning node_copy.children = root.children creates a shallow copy where both trees share the same child nodes. Each child must be recursively cloned.

# Wrong: Shares children with original
node_copy.children = root.children

# Correct: Clone each child
for child in root.children:
    node_copy.children.append(self.cloneTree(child))