Clone N-ary Tree

Clone N-ary Tree 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.

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
• All coding practice problems

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