We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Clone N-ary Tree

Number: 1634

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given the root of an N-ary tree, create a deep copy (clone) of the tree. Each node in the tree contains an integer value and a list of its children. The goal is to replicate the tree such that a completely new tree structure is returned, with no shared references between the original and the copy.

Key Insights

  • The tree is N-ary, meaning every node can have multiple children.
  • A deep copy requires creating new nodes for each node in the tree.
  • Both DFS (recursive) or BFS (iterative) traversals can be used to clone the tree.
  • The overall time complexity is O(N) since each node is visited once.
  • We can follow similar cloning techniques used in cloning graphs, using either recursion or an auxiliary data structure like a queue.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, since each node is visited exactly once. Space Complexity: O(N), accounting for the recursive call stack (or an explicit queue in BFS) and the space needed to store the clone.

Solution

We perform a DFS traversal starting from the root node. For each node we encounter, we:

  1. Create a new node with the same value.
  2. Recursively clone all its children and attach the cloned children to the new node. This approach ensures that every original node is copied into a new node and that the parent-child relationships are preserved. Edge cases such as an empty tree (null root) are also handled by returning null immediately.

Code Solutions

# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

def cloneTree(root):
    # Base case: if root is None, return None.
    if root is None:
        return None
        
    # Create a clone for the current node.
    cloned_node = Node(root.val)
    
    # Recursively clone each child and add it to the cloned_node's children list.
    for child in root.children:
        cloned_child = cloneTree(child)
        cloned_node.children.append(cloned_child)
    
    # Return the cloned node.
    return cloned_node

# Example usage:
# original_tree = Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)])
# cloned_tree = cloneTree(original_tree)
← Back to All Questions