Jobs

Interviews

Discussions

Clone N-ary Tree

Medium

Asked by:

2 views

Topics:

TreesRecursion

Given the root of a 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 breadth first traversal, each level 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 number of nodes in the n-ary tree is less than or equal to 10⁴.

Try coding it in LeetCode

Clone N-ary Tree

Medium

Asked by:

2 views

Topics:

TreesRecursion

Given the root of a 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 breadth first traversal, each level 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 number of nodes in the n-ary tree is less than or equal to 10⁴.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the N-ary tree be empty or null?
What are the data types and possible values of the nodes in the tree?
Should the cloned tree be a deep copy or a shallow copy?
Is the structure of the input tree guaranteed to be a valid N-ary tree, or do I need to handle potential malformed trees?
Can the original tree be modified after cloning, and should the cloned tree be independent of any subsequent changes to the original?

Brute Force Solution

Approach

To clone an N-ary tree using a brute force method, we will create a new tree node by node. For each node in the original tree, we will find its exact match in the new tree and then create copies of all its children in the same relative order.

Here's how the algorithm would work step-by-step:

Start by creating a new root node for the cloned tree that mirrors the root node of the original tree.
For each node in the original tree, find the corresponding node in the newly created (cloned) tree. Since it's the brute force approach, you might need to check every node in the cloned tree to find its match.
Once you've found the matching node in the cloned tree, create new child nodes for it, making sure each child is an exact copy of the original node's child.
Repeat the above process for each child node. This means you'll need to find the match of the newly created child node in the original tree, and then create its children in the cloned tree.
Continue this process, node by node, until you have traversed every node in the original tree and replicated it in the cloned tree.

Code Implementation

class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

def clone_n_ary_tree(root):
    if not root:
        return None

    cloned_root = Node(root.val)

    # Dictionary to store mapping between original and cloned nodes
    node_map = {root: cloned_root}

    queue = [root]

    while queue:
        current_node = queue.pop(0)
        cloned_current_node = node_map[current_node]

        for child in current_node.children:
            cloned_child = Node(child.val)
            cloned_current_node.children.append(cloned_child)
            node_map[child] = cloned_child
            queue.append(child)

    return cloned_root

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n nodes in the original N-ary tree. For each node in the original tree, it searches for its corresponding node in the cloned tree, potentially visiting every node in the cloned tree, which can have up to n nodes in the worst case. Therefore, the nested operation of iterating through the original tree and searching in the cloned tree leads to n * n operations. This simplifies to O(n²).

Space Complexity

O(N) – The brute force approach described requires, at worst, searching the entire cloned tree to find the matching node for each node in the original tree. Since we might traverse the cloned tree in its entirety to find each node, we need a way to store these nodes, requiring space proportional to the number of nodes in the cloned tree. Because the cloned tree contains N nodes (where N is the number of nodes in the original tree), this search operation can potentially use auxiliary space proportional to N. Thus, the space complexity for the brute force approach is O(N).

Optimal Solution

Approach

To create a perfect copy of a tree where each node can have many children, we'll walk through the original tree and create new nodes to match. We'll use a simple, organized way to keep track of which original node corresponds to its copy.

Here's how the algorithm would work step-by-step:

Check if the original tree is empty. If it is, there's nothing to copy, so we're done.
If the original tree has a root node, create a brand-new node that's an exact copy of it. This will be the root of our new tree.
Create a system to easily find the matching copy for each node in the original tree. Think of it like a simple lookup table.
Go through each node in the original tree, one by one.
For each node, create copies of all its children and link them to the copied parent node in our new tree.
Use our lookup system to make sure we're connecting the right original nodes to their corresponding copies.
Once we've visited all the nodes in the original tree and created their copies and links, our new tree is complete.

Code Implementation

class NAryNode:
    def __init__(self, value):
        self.value = value
        self.children = []

def clone_n_ary_tree(root):
    if not root:
        return None

    cloned_root = NAryNode(root.value)

    # Maps original nodes to their clones.
    node_map = {root: cloned_root}

    nodes_to_process = [root]

    while nodes_to_process:
        current_node = nodes_to_process.pop(0)
        cloned_current_node = node_map[current_node]

        # Iterate through children to clone
        for child in current_node.children:
            cloned_child = NAryNode(child.value)
            cloned_current_node.children.append(cloned_child)

            # Maintain the mapping for further cloning.
            node_map[child] = cloned_child
            nodes_to_process.append(child)

    # Return the root of the cloned tree.
    return cloned_root

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node of the n-ary tree exactly once. For each node visited, a constant amount of work is performed: creating a new node and linking it to its parent. The lookup table ensures that finding the corresponding copy takes constant time. Therefore, the time complexity is directly proportional to the number of nodes in the tree, resulting in O(n).

Space Complexity

O(N) – The algorithm uses a lookup table to store the mapping between original nodes and their clones. In the worst case, all N nodes of the original tree will be present in the lookup table simultaneously. This lookup table consumes space proportional to the number of nodes in the tree, resulting in O(N) auxiliary space. Additionally, a recursive (or iterative using queue) traversal will use space up to O(W), where W is the maximum width of the N-ary tree. Assuming maximum width can be N, the total space will be O(N) + O(N) = O(N).

Edge Cases

Case	How to Handle
Null root node	Return null immediately as there is nothing to clone.
Root node with no children	Clone the root and return it, as it's a valid single-node tree.
Deeply nested tree, potential stack overflow with recursion	Consider iterative approach using a queue to avoid stack overflow for extremely deep trees.
Very wide tree (root with many children)	Check for memory constraints when creating many child nodes in the cloned tree.
Tree with self-referential children (cycles, although not strictly a tree)	The cloning process should not create cycles in the clone, and cyclical input indicates invalid input and might require a cycle detection mechanism to prevent infinite loops.
Node data containing null values or special characters	Ensure node data is handled correctly during copying, including null or special characters, preventing unexpected behavior.
Large integer values in the node data, close to integer limits.	Handle potential overflow in arithmetic operations if node data is used in calculations during the cloning process; use appropriate data types.
Memory allocation failure during node creation	Handle potential memory allocation errors when creating new nodes; return null or throw exception as appropriate to indicate failure.

Null root node

How to Handle:

Return null immediately as there is nothing to clone.

Root node with no children

How to Handle:

Clone the root and return it, as it's a valid single-node tree.

Deeply nested tree, potential stack overflow with recursion

How to Handle:

Consider iterative approach using a queue to avoid stack overflow for extremely deep trees.

Very wide tree (root with many children)

How to Handle:

Check for memory constraints when creating many child nodes in the cloned tree.

Tree with self-referential children (cycles, although not strictly a tree)

How to Handle:

The cloning process should not create cycles in the clone, and cyclical input indicates invalid input and might require a cycle detection mechanism to prevent infinite loops.

Node data containing null values or special characters

How to Handle:

Ensure node data is handled correctly during copying, including null or special characters, preventing unexpected behavior.

Large integer values in the node data, close to integer limits.

How to Handle:

Handle potential overflow in arithmetic operations if node data is used in calculations during the cloning process; use appropriate data types.

Memory allocation failure during node creation

How to Handle:

Handle potential memory allocation errors when creating new nodes; return null or throw exception as appropriate to indicate failure.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the N-ary tree be empty or null?
What are the data types and possible values of the nodes in the tree?
Should the cloned tree be a deep copy or a shallow copy?
Is the structure of the input tree guaranteed to be a valid N-ary tree, or do I need to handle potential malformed trees?
Can the original tree be modified after cloning, and should the cloned tree be independent of any subsequent changes to the original?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by creating a new root node for the cloned tree that mirrors the root node of the original tree.
For each node in the original tree, find the corresponding node in the newly created (cloned) tree. Since it's the brute force approach, you might need to check every node in the cloned tree to find its match.
Once you've found the matching node in the cloned tree, create new child nodes for it, making sure each child is an exact copy of the original node's child.
Repeat the above process for each child node. This means you'll need to find the match of the newly created child node in the original tree, and then create its children in the cloned tree.
Continue this process, node by node, until you have traversed every node in the original tree and replicated it in the cloned tree.

Code Implementation

class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

def clone_n_ary_tree(root):
    if not root:
        return None

    cloned_root = Node(root.val)

    # Dictionary to store mapping between original and cloned nodes
    node_map = {root: cloned_root}

    queue = [root]

    while queue:
        current_node = queue.pop(0)
        cloned_current_node = node_map[current_node]

        for child in current_node.children:
            cloned_child = Node(child.val)
            cloned_current_node.children.append(cloned_child)
            node_map[child] = cloned_child
            queue.append(child)

    return cloned_root

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Check if the original tree is empty. If it is, there's nothing to copy, so we're done.
If the original tree has a root node, create a brand-new node that's an exact copy of it. This will be the root of our new tree.
Create a system to easily find the matching copy for each node in the original tree. Think of it like a simple lookup table.
Go through each node in the original tree, one by one.
For each node, create copies of all its children and link them to the copied parent node in our new tree.
Use our lookup system to make sure we're connecting the right original nodes to their corresponding copies.
Once we've visited all the nodes in the original tree and created their copies and links, our new tree is complete.

Code Implementation

class NAryNode:
    def __init__(self, value):
        self.value = value
        self.children = []

def clone_n_ary_tree(root):
    if not root:
        return None

    cloned_root = NAryNode(root.value)

    # Maps original nodes to their clones.
    node_map = {root: cloned_root}

    nodes_to_process = [root]

    while nodes_to_process:
        current_node = nodes_to_process.pop(0)
        cloned_current_node = node_map[current_node]

        # Iterate through children to clone
        for child in current_node.children:
            cloned_child = NAryNode(child.value)
            cloned_current_node.children.append(cloned_child)

            # Maintain the mapping for further cloning.
            node_map[child] = cloned_child
            nodes_to_process.append(child)

    # Return the root of the cloned tree.
    return cloned_root

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null root node	Return null immediately as there is nothing to clone.
Root node with no children	Clone the root and return it, as it's a valid single-node tree.
Deeply nested tree, potential stack overflow with recursion	Consider iterative approach using a queue to avoid stack overflow for extremely deep trees.
Very wide tree (root with many children)	Check for memory constraints when creating many child nodes in the cloned tree.
Tree with self-referential children (cycles, although not strictly a tree)	The cloning process should not create cycles in the clone, and cyclical input indicates invalid input and might require a cycle detection mechanism to prevent infinite loops.
Node data containing null values or special characters	Ensure node data is handled correctly during copying, including null or special characters, preventing unexpected behavior.
Large integer values in the node data, close to integer limits.	Handle potential overflow in arithmetic operations if node data is used in calculations during the cloning process; use appropriate data types.
Memory allocation failure during node creation	Handle potential memory allocation errors when creating new nodes; return null or throw exception as appropriate to indicate failure.

Null root node

How to Handle:

Return null immediately as there is nothing to clone.

Root node with no children

How to Handle:

Clone the root and return it, as it's a valid single-node tree.

Deeply nested tree, potential stack overflow with recursion

How to Handle:

Consider iterative approach using a queue to avoid stack overflow for extremely deep trees.

Very wide tree (root with many children)

How to Handle:

Check for memory constraints when creating many child nodes in the cloned tree.

Tree with self-referential children (cycles, although not strictly a tree)

How to Handle:

The cloning process should not create cycles in the clone, and cyclical input indicates invalid input and might require a cycle detection mechanism to prevent infinite loops.

Node data containing null values or special characters

How to Handle:

Ensure node data is handled correctly during copying, including null or special characters, preventing unexpected behavior.

Large integer values in the node data, close to integer limits.

How to Handle:

Handle potential overflow in arithmetic operations if node data is used in calculations during the cloning process; use appropriate data types.

Memory allocation failure during node creation

How to Handle:

Handle potential memory allocation errors when creating new nodes; return null or throw exception as appropriate to indicate failure.