1490. Clone N-ary Tree

Clone N-ary Tree (LeetCode 1490) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Deep Copy / Cloning subpattern.

How to solve Clone N-ary Tree

Clone N-ary Tree is a Graph Deep Copy and Cloning problem, part of Graph Traversal Patterns (DFS & BFS). Learn to deep copy and clone graph structures using DFS/BFS with visited mapping.

Work towards the solution in these steps:

1. Consider which graph traversal technique (DFS or BFS) could be used to visit every node in the N-ary tree systematically.
2. Think about how you would create a new node for each original node while preserving the tree structure during traversal.
3. Remember that each node has multiple children; ensure your traversal method handles a list of children correctly.

The reference solution runs in O(n) time and O(h) space.

The Clone N-ary Tree solution and editorial walks through the full approach with reference code.

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 children; } Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

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

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, 10^4].

Topics and companies

Topics: Hash Table, Tree, Depth-first Search, Breadth-first Search.

Reported in interviews at Amazon.

How to practise Clone N-ary Tree on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(h) space.

Open Clone N-ary Tree in the code editor, or read the Clone N-ary Tree editorial for a worked solution with its approach and complexity analysis.

Where Clone N-ary Tree sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Deep Copy / Cloning subpattern
• The full DSA patterns sheet

Problems related to Clone N-ary Tree

Other problems that use the same Deep Copy / Cloning and Graph Traversal Patterns (DFS & BFS) techniques:

• Clone Graph — Medium, same subpattern
• Copy List with Random Pointer — Medium, same subpattern
• Find the City With the Smallest Number of Neighbors at a Threshold Distance — Medium, same subpattern
• Accounts Merge — Medium, same pattern
• Alien Dictionary — Hard, same pattern
• All Paths from Source Lead to Destination — Medium, same pattern

Clone N-ary Tree FAQ