Clone N-ary Tree
Medium · Graphs · Explanation and code example
BFS
How it works
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.
Steps
- If root is
null, returnnull. - Create the cloned root and enqueue the pair (root, new_root).
- 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).
- Return the cloned root.
Complexity
- Time complexity:
O(M) - Space complexity:
O(M)
Where
Mis the number of nodes in the input tree.
Things to watch for
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.
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.
Python code example
from collections import deque
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
C++ code example
class Solution {
public:
Node* cloneTree(Node* root) {
if (!root) {
return root;
}
Node* new_root = new Node(root->val);
// Starting point to kick off the BFS visits.
queue<pair<Node*, Node*>> q;
q.push({root, new_root});
while (!q.empty()) {
// Get the element from the head of the queue.
auto [old_node, new_node] = q.front();
q.pop();
for (Node* child_node : old_node->children) {
Node* new_child_node = new Node(child_node->val);
// Make a copy for each child node.
new_node->children.push_back(new_child_node);
// Schedule a visit to copy the child nodes of each child node.
q.push({child_node, new_child_node});
}
}
return new_root;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.