Skip to main content
Talentd

Clone N-ary Tree - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableTreeDepth-First SearchBreadth-First Search4 min readAsked at: Amazon
Practice this problem

Problem Statement

Given a root of an N-ary tree, return a deep copy (clone) of the tree.

Each node in the n-ary tree contains a val (int) and a list (List[Node]) of its children.

class Node {
    public int val;
    public List<Node> children;
}

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

 

Example 1:

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

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]
Output: [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]

 

Constraints:

  • The depth of the n-ary tree is less than or equal to 1000.
  • The total number of nodes is between [0, 104].

 

Follow up: Can your solution work for the graph problem?

Approach Overview

Problem Overview: You receive the root of an N-ary tree and must return a deep copy of it. Every node in the new tree must be newly created, but the structure and values must match the original tree exactly.

An N-ary tree node contains a value and a list of children. Cloning requires recreating each node and rebuilding the children relationships. The key rule: never reuse existing nodes from the original tree. Each node must be duplicated.

Approach 1: Depth-First Search Clone (DFS) (Time: O(n), Space: O(n))

The most common solution performs a recursive depth-first search. For each node you visit, create a new node with the same value. Then recursively clone every child and append the returned clones to the new node’s children list. Because an N-ary tree has no cycles, you do not need a visited set or hash table. Each node is processed exactly once. The recursion stack may grow up to the tree height, giving O(h) stack usage, which in the worst case becomes O(n).

The key insight: cloning naturally mirrors traversal. When DFS reaches a node, construct its copy immediately and recursively build its subtree. The returned cloned children automatically rebuild the structure.

Approach 2: Breadth-First Search Clone (BFS) (Time: O(n), Space: O(n))

You can also clone the tree using breadth-first search. Start by creating a clone of the root and pushing the pair (original, clone) into a queue. For every node dequeued, iterate through its children, create cloned child nodes, attach them to the cloned parent, and enqueue the pair for further processing. BFS processes the tree level by level and constructs the same hierarchy in the new tree.

This approach avoids recursion and uses an explicit queue. Space usage comes from the queue storing nodes from the current level. The cloning logic is still straightforward: each original node produces exactly one cloned node.

Recommended for interviews: The recursive DFS clone is what most interviewers expect. It is concise, clearly mirrors the tree structure, and demonstrates strong understanding of tree traversal. BFS works equally well and is useful when recursion depth could be large. Mentioning both approaches shows deeper understanding of traversal strategies.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Depth-First Search (Recursive Clone)O(n)O(n)Most common interview solution. Clean and directly mirrors tree structure.
Breadth-First Search (Queue)O(n)O(n)When avoiding recursion or handling very deep trees.

Video Solution

LeetCode 1490. Clone N-ary Tree - Interview Prep Ep 110 • Fisher Coder • 1,076 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Clone N-ary Tree easy or hard?
Clone N-ary Tree is generally considered a medium difficulty problem. The challenge is understanding deep copying and correctly rebuilding the children relationships while traversing the tree using DFS or BFS.
Clone N-ary Tree Python/Java solution
Python, Java, C++, and Go implementations follow the same idea: create a new node, recursively or iteratively clone each child, and append those clones to the new node’s children list. The algorithm runs in O(n) time and builds a full deep copy of the tree.
How to solve Clone N-ary Tree in O(n)?
Traverse the tree using DFS or BFS. Whenever you visit a node, create a new node with the same value and attach cloned versions of its children. Because every node is processed once and edges are visited once, the overall complexity remains O(n).
What is the best approach for Clone N-ary Tree?
Depth-First Search (DFS) recursion is the most common approach. For each node, create a new node with the same value and recursively clone all children. The algorithm visits each node exactly once, giving O(n) time and O(n) space due to recursion stack and the cloned tree.
Is Clone N-ary Tree asked at Google/Amazon/Meta?
Tree cloning and deep copy problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations include cloning binary trees, graphs, or N-ary trees to test traversal and data structure fundamentals.
What data structure is used in Clone N-ary Tree?
The primary data structure is an N-ary tree with nodes containing a value and a list of children. DFS solutions rely on recursion, while BFS solutions use a queue to process nodes level by level.
What is the time complexity of Clone N-ary Tree?
The time complexity is O(n), where n is the number of nodes in the tree. Each node is visited exactly once during traversal, and a constant amount of work is done to create the cloned node and attach its children.

Ready to solve this problem?

Practice Clone N-ary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Clone Binary Tree With Random Pointer

Next

Clone Graph