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.

Description Hints 2 Solution Video 12:45

1490. Clone N-ary Tree

Medium83.2% acceptance1 companyPremium elsewhere, free here

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

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

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

Traverse the tree, keep a hashtable with you and create a clone node for each node in the tree.

Hint 2

Start traversing the original tree again and connect each child pointer in the cloned tree the same way as the original tree with the help of the hashtable.

12:45

Still stuck?Read the written solution, or watch a walkthrough.

Open solution