Problem Statement

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

Each node in the N-ary tree has an integer value (val) and a list of its children (children). The deep copy should have the exact structure and values as the original tree but should not share any references with it.

Examples

Example 1

• Input: root = [1, null, 2, 3, 4, 5, null, 6, 7, null, 8]

• Expected Output: [1, null, 2, 3, 4, 5, null, 6, 7, null, 8]
• Justification:
  • The tree has multiple levels, where each node has a different number of children. The cloned tree should maintain the same structure with values intact.

Example 2

• Input: root = [7, null, 9, null, 11, 12, null, 14, 15, null, 16]

• Expected Output: [7, null, 9, null, 11, 12, null, 14, 15, null, 16]
• Justification:
  • The clone of tree is created.

Example 3

• Input: root = [4, null, 5, 6, 7, 8, null, 9, null, 10, 11, 12]

• Expected Output: [4, null, 5, 6, 7, 8, null, 9, null, 10, 11, 12]
• Justification:
  • The deep copy of the original tree is created and returned.

Constraints:

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

Try it yourself

Try solving this question here: