1490. Clone N-ary Tree - Solution & Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Tree Traversal - Understanding recursive and iterative approaches to visit all nodes in a tree
N-ary Tree Structure - Working with trees where each node can have any number of children
Stack/Queue Data Structures - Using stacks for DFS and queues for BFS in iterative solutions

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

Base case: If the node is null, return null.
Create a new node with the same value as the current node.
For each child of the current node, recursively clone the child and add it to the new node's children list.
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

class Solution {
    public Node cloneTree(Node root) {
        // Base case: empty node.
        if (root == null) {
            return root;
        }

        // First, copy the node itself.
        Node nodeCopy = new Node(root.val);

        // Then, recursively clone the sub-trees.
        for (Node child : root.children) {
            nodeCopy.children.add(this.cloneTree(child));
        }

        return nodeCopy;
    }
}

class Solution {
public:
    Node* cloneTree(Node* root) {
        // Base case: empty node.
        if (!root) {
            return root;
        }
        
        // First, copy the node itself.
        Node* node_copy = new Node(root->val);
        
        // Then, recursively clone the sub-trees.
        for (Node* child : root->children) {
            node_copy->children.push_back(cloneTree(child));
        }
        
        return node_copy;
    }
};

class Solution {
    /**
     * @param {_Node|null} root
     * @return {_Node|null}
     */
    cloneTree(root) {
        // Base case: empty node.
        if (!root) {
            return root;
        }

        // First, copy the node itself.
        const node_copy = new Node(root.val);

        // Then, recursively clone the sub-trees.
        for (const child of root.children) {
            node_copy.children.push(this.cloneTree(child));
        }

        return node_copy;
    }
}

/*
// Definition for a Node.
public class Node {
    public int val;
    public IList<Node> children;

    public Node() {
        val = 0;
        children = new List<Node>();
    }

    public Node(int _val) {
        val = _val;
        children = new List<Node>();
    }
}
*/

public class Solution {
    public Node CloneTree(Node root) {
        // Base case: empty node.
        if (root == null) {
            return root;
        }

        // First, copy the node itself.
        Node nodeCopy = new Node(root.val);

        // Then, recursively clone the sub-trees.
        foreach (Node child in root.children) {
            nodeCopy.children.Add(CloneTree(child));
        }

        return nodeCopy;
    }
}

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

func cloneTree(root *Node) *Node {
    // Base case: empty node.
    if root == nil {
        return root
    }

    // First, copy the node itself.
    nodeCopy := &Node{Val: root.Val}

    // Then, recursively clone the sub-trees.
    for _, child := range root.Children {
        nodeCopy.Children = append(nodeCopy.Children, cloneTree(child))
    }

    return nodeCopy
}

/**
 * Definition for a Node.
 * class Node(var `val`: Int) {
 *     var children: List<Node?> = listOf()
 * }
 */

class Solution {
    fun cloneTree(root: Node?): Node? {
        // Base case: empty node.
        if (root == null) {
            return root
        }

        // First, copy the node itself.
        val nodeCopy = Node(root.`val`)

        // Then, recursively clone the sub-trees.
        nodeCopy.children = root.children.map { cloneTree(it) }

        return nodeCopy
    }
}

/**
 * Definition for a Node.
 * public class Node {
 *     public var val: Int
 *     public var children: [Node]
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.children = []
 *     }
 * }
 */

class Solution {
    func cloneTree(_ root: Node?) -> Node? {
        // Base case: empty node.
        guard let root = root else {
            return nil
        }

        // First, copy the node itself.
        let nodeCopy = Node(root.val)

        // Then, recursively clone the sub-trees.
        for child in root.children {
            if let clonedChild = cloneTree(child) {
                nodeCopy.children.append(clonedChild)
            }
        }

        return nodeCopy
    }
}

impl Solution {
    pub fn clone_tree(root: Option<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> {
        let root = root?;
        let node = root.borrow();
        let node_copy = Rc::new(RefCell::new(Node::new(node.val)));

        for child in &node.children {
            if let Some(cloned) = Self::clone_tree(child.clone()) {
                node_copy.borrow_mut().children.push(Some(cloned));
            }
        }

        Some(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

If root is null, return null.
Create the cloned root and push the pair (root, new_root) onto a stack.
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.
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

class Solution {
    public Node cloneTree(Node root) {
        if (root == null) {
            return root;
        }

        Node newRoot = new Node(root.val);

        // Here we used the ArrayDeque instead of the Queue class,
        // which is a more efficient implementation of queue data structure.
        Deque<Node[]> stack = new ArrayDeque<>();

        // Starting point to kick off the DFS visits.
        stack.addLast(new Node[]{root, newRoot});

        while (!stack.isEmpty()) {
            Node[] nodePair = stack.pop();
            Node oldNode = nodePair[0];
            Node newNode = nodePair[1];
            for (Node childNode : oldNode.children) {
                Node newChildNode = new Node(childNode.val);

                // Make a copy for each child node.
                newNode.children.add(newChildNode);

                // Schedule a visit to copy the child nodes of each child node.
                stack.push(new Node[]{childNode, newChildNode});
            }
        }

        return newRoot;
    }
}

class Solution {
public:
    Node* cloneTree(Node* root) {
        if (!root) {
            return root;
        }
        
        Node* new_root = new Node(root->val);
        // Starting point to kick off the DFS visits.
        stack<pair<Node*, Node*>> st;
        st.push({root, new_root});
        
        while (!st.empty()) {
            auto [old_node, new_node] = st.top();
            st.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.
                st.push({child_node, new_child_node});
            }
        }
        
        return new_root;
    }
};

class Solution {
    /**
     * @param {_Node|null} node
     * @return {_Node|null}
     */
    cloneTree(root) {
        if (!root) {
            return root;
        }

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

        while (stack.length > 0) {
            const [old_node, new_node] = stack.pop();

            for (const child_node of old_node.children) {
                const new_child_node = new Node(child_node.val);
                // Make a copy for each child node.
                new_node.children.push(new_child_node);
                // Schedule a visit to copy the child nodes of each child node.
                stack.push([child_node, new_child_node]);
            }
        }

        return new_root;
    }
}

public class Solution {
    public Node CloneTree(Node root) {
        if (root == null) {
            return root;
        }

        Node newRoot = new Node(root.val);
        // Starting point to kick off the DFS visits.
        Stack<Node[]> stack = new Stack<Node[]>();
        stack.Push(new Node[] { root, newRoot });

        while (stack.Count > 0) {
            Node[] nodePair = stack.Pop();
            Node oldNode = nodePair[0];
            Node newNode = nodePair[1];

            foreach (Node childNode in oldNode.children) {
                Node newChildNode = new Node(childNode.val);
                // Make a copy for each child node.
                newNode.children.Add(newChildNode);
                // Schedule a visit to copy the child nodes of each child node.
                stack.Push(new Node[] { childNode, newChildNode });
            }
        }

        return newRoot;
    }
}

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

    newRoot := &Node{Val: root.Val}
    // Starting point to kick off the DFS visits.
    stack := [][2]*Node{{root, newRoot}}

    for len(stack) > 0 {
        pair := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        oldNode, newNode := pair[0], pair[1]

        for _, childNode := range oldNode.Children {
            newChildNode := &Node{Val: childNode.Val}
            // Make a copy for each child node.
            newNode.Children = append(newNode.Children, newChildNode)
            // Schedule a visit to copy the child nodes of each child node.
            stack = append(stack, [2]*Node{childNode, newChildNode})
        }
    }

    return newRoot
}

class Solution {
    fun cloneTree(root: Node?): Node? {
        if (root == null) {
            return root
        }

        val newRoot = Node(root.`val`)
        // Starting point to kick off the DFS visits.
        val stack = ArrayDeque<Pair<Node, Node>>()
        stack.addLast(Pair(root, newRoot))

        while (stack.isNotEmpty()) {
            val (oldNode, newNode) = stack.removeLast()
            val newChildren = mutableListOf<Node?>()

            for (childNode in oldNode.children) {
                if (childNode != null) {
                    val newChildNode = Node(childNode.`val`)
                    // Make a copy for each child node.
                    newChildren.add(newChildNode)
                    // Schedule a visit to copy the child nodes of each child node.
                    stack.addLast(Pair(childNode, newChildNode))
                }
            }
            newNode.children = newChildren
        }

        return newRoot
    }
}

class Solution {
    func cloneTree(_ root: Node?) -> Node? {
        guard let root = root else {
            return nil
        }

        let newRoot = Node(root.val)
        // Starting point to kick off the DFS visits.
        var stack: [(Node, Node)] = [(root, newRoot)]

        while !stack.isEmpty {
            let (oldNode, newNode) = stack.removeLast()

            for childNode in oldNode.children {
                let newChildNode = Node(childNode.val)
                // Make a copy for each child node.
                newNode.children.append(newChildNode)
                // Schedule a visit to copy the child nodes of each child node.
                stack.append((childNode, newChildNode))
            }
        }

        return newRoot
    }
}

impl Solution {
    pub fn clone_tree(root: Option<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> {
        let root = root?;
        let new_root = Rc::new(RefCell::new(Node::new(root.borrow().val)));
        let mut stack: Vec<(Rc<RefCell<Node>>, Rc<RefCell<Node>>)> = vec![(root.clone(), new_root.clone())];

        while let Some((old_node, new_node)) = stack.pop() {
            let old_borrowed = old_node.borrow();
            for child in &old_borrowed.children {
                if let Some(child_rc) = child {
                    let new_child = Rc::new(RefCell::new(Node::new(child_rc.borrow().val)));
                    new_node.borrow_mut().children.push(Some(new_child.clone()));
                    stack.push((child_rc.clone(), new_child));
                }
            }
        }

        Some(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

If root is null, return null.
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.

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

class Solution {
    public Node cloneTree(Node root) {
        if (root == null) {
            return root;
        }

        Node newRoot = new Node(root.val);

        // Starting point to kick off the BFS visits.
        // Here we used the ArrayDeque instead of the Queue class,
        // which is a more efficient implementation of queue data structure.
        Deque<Node[]> queue = new ArrayDeque<>();
        queue.addLast(new Node[]{root, newRoot});

        while (!queue.isEmpty()) {
            Node[] nodePair = queue.removeFirst();

            Node oldNode = nodePair[0];
            Node newNode = nodePair[1];
            for (Node childNode : oldNode.children) {
                Node newChildNode = new Node(childNode.val);

                // Make a copy for each child node.
                newNode.children.add(newChildNode);

                // Schedule a visit to copy the child nodes of each child node.
                queue.addLast(new Node[]{childNode, newChildNode});
            }
        }

        return newRoot;
    }
}

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;
    }
};

class Solution {
    /**
     * @param {_Node|null} root
     * @return {_Node|null}
     */
    cloneTree(root) {
        if (!root) {
            return root;
        }

        const new_root = new Node(root.val);
        // Starting point to kick off the BFS visits.
        const queue = [[root, new_root]];

        while (queue.length > 0) {
            // Get the element from the head of the queue.
            const [old_node, new_node] = queue.shift();

            for (const child_node of old_node.children) {
                const new_child_node = new Node(child_node.val);
                // Make a copy for each child node.
                new_node.children.push(new_child_node);
                // Schedule a visit to copy the child nodes of each child node.
                queue.push([child_node, new_child_node]);
            }
        }

        return new_root;
    }
}

public class Solution {
    public Node CloneTree(Node root) {
        if (root == null) {
            return root;
        }

        Node newRoot = new Node(root.val);
        // Starting point to kick off the BFS visits.
        Queue<Node[]> queue = new Queue<Node[]>();
        queue.Enqueue(new Node[] { root, newRoot });

        while (queue.Count > 0) {
            Node[] nodePair = queue.Dequeue();
            Node oldNode = nodePair[0];
            Node newNode = nodePair[1];

            foreach (Node childNode in oldNode.children) {
                Node newChildNode = new Node(childNode.val);
                // Make a copy for each child node.
                newNode.children.Add(newChildNode);
                // Schedule a visit to copy the child nodes of each child node.
                queue.Enqueue(new Node[] { childNode, newChildNode });
            }
        }

        return newRoot;
    }
}

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

    newRoot := &Node{Val: root.Val}
    // Starting point to kick off the BFS visits.
    queue := [][2]*Node{{root, newRoot}}

    for len(queue) > 0 {
        // Get the element from the head of the queue.
        pair := queue[0]
        queue = queue[1:]
        oldNode, newNode := pair[0], pair[1]

        for _, childNode := range oldNode.Children {
            newChildNode := &Node{Val: childNode.Val}
            // Make a copy for each child node.
            newNode.Children = append(newNode.Children, newChildNode)
            // Schedule a visit to copy the child nodes of each child node.
            queue = append(queue, [2]*Node{childNode, newChildNode})
        }
    }

    return newRoot
}

class Solution {
    fun cloneTree(root: Node?): Node? {
        if (root == null) {
            return root
        }

        val newRoot = Node(root.`val`)
        // Starting point to kick off the BFS visits.
        val queue = ArrayDeque<Pair<Node, Node>>()
        queue.addLast(Pair(root, newRoot))

        while (queue.isNotEmpty()) {
            val (oldNode, newNode) = queue.removeFirst()
            val newChildren = mutableListOf<Node?>()

            for (childNode in oldNode.children) {
                if (childNode != null) {
                    val newChildNode = Node(childNode.`val`)
                    // Make a copy for each child node.
                    newChildren.add(newChildNode)
                    // Schedule a visit to copy the child nodes of each child node.
                    queue.addLast(Pair(childNode, newChildNode))
                }
            }
            newNode.children = newChildren
        }

        return newRoot
    }
}

class Solution {
    func cloneTree(_ root: Node?) -> Node? {
        guard let root = root else {
            return nil
        }

        let newRoot = Node(root.val)
        // Starting point to kick off the BFS visits.
        var queue: [(Node, Node)] = [(root, newRoot)]

        while !queue.isEmpty {
            // Get the element from the head of the queue.
            let (oldNode, newNode) = queue.removeFirst()

            for childNode in oldNode.children {
                let newChildNode = Node(childNode.val)
                // Make a copy for each child node.
                newNode.children.append(newChildNode)
                // Schedule a visit to copy the child nodes of each child node.
                queue.append((childNode, newChildNode))
            }
        }

        return newRoot
    }
}

impl Solution {
    pub fn clone_tree(root: Option<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> {
        let root = root?;
        let new_root = Rc::new(RefCell::new(Node::new(root.borrow().val)));
        let mut queue: VecDeque<(Rc<RefCell<Node>>, Rc<RefCell<Node>>)> = VecDeque::new();
        queue.push_back((root.clone(), new_root.clone()));

        while let Some((old_node, new_node)) = queue.pop_front() {
            let old_borrowed = old_node.borrow();
            for child in &old_borrowed.children {
                if let Some(child_rc) = child {
                    let new_child = Rc::new(RefCell::new(Node::new(child_rc.borrow().val)));
                    new_node.borrow_mut().children.push(Some(new_child.clone()));
                    queue.push_back((child_rc.clone(), new_child.clone()));
                }
            }
        }

        Some(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))