hard Clone N-ary Tree

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

Solution

To solve this problem, we will use a Depth-First Search (DFS) approach to traverse the N-ary tree and construct a deep copy. The core idea is to recursively visit each node, creating a new node with the same value and then cloning its children by recursively calling the same function. This approach is effective because it ensures that every node is visited once, and a new corresponding node is created without sharing any references between the original and cloned nodes.

The DFS approach is the most efficient for this problem as it allows us to explore each node and its descendants immediately, which is optimal for constructing a clone of an N-ary tree. Additionally, this method guarantees that the recursion will handle nodes systematically, preserving the exact structure and values as required for a deep copy.

Step-by-Step Algorithm

• Initialize a recursive function cloneNode(node) that takes a node as input.
• Base Case: If the input node is null, return null (end of branch).
• Create a new node (newNode) with the same value as the input node.
• Iterate over the list of children for the input node.
  • For each child, recursively call cloneNode(child) to clone its subtree.
  • Append the cloned subtree to newNode's children list.
• Return the newly created node (newNode), which represents the root of the cloned subtree.

Algorithm Walkthrough

Given the input: root = [1, null, 2, 3, 4, 5, null, 6, 7, null, 8]

1. Start at the root node (1):

   • The root node has a value of 1.
   • A new node, newNode(1), is created with the same value (1).
   • The root node (1) has four children: 2, 3, 4, and 5. The cloning process will recursively clone each child.

2. Clone the first child of node 1, which is node 2:

   • A new node, newNode(2), is created with the value 2.
   • Node 2 has two children: 6 and 7. The cloning process continues to recursively clone these children.

3. Clone the children of node 2, starting with node 6:

   • A new node, newNode(6), is created with the value 6.
   • Node 6 has no children, so the recursion ends here for this branch. newNode(6) is added to the children list of newNode(2).

4. Clone the next child of node 2, which is node 7:

   • A new node, newNode(7), is created with the value 7.
   • Node 7 has no children, so the recursion ends here for this branch. newNode(7) is added to the children list of newNode(2).

5. Finish cloning node 2:

   • The cloned node newNode(2) now has two children: newNode(6) and newNode(7).
   • newNode(2) is added to the children list of newNode(1).

6. Clone the next child of node 1, which is node 3:

   • A new node, newNode(3), is created with the value 3.
   • Node 3 has one child: 8. The cloning process will now recursively clone this child.

7. Clone the child of node 3, which is node 8:

   • A new node, newNode(8), is created with the value 8.
   • Node 8 has no children, so the recursion ends here for this branch. newNode(8) is added to the children list of newNode(3).

8. Finish cloning node 3:

   • The cloned node newNode(3) now has one child: newNode(8).
   • newNode(3) is added to the children list of newNode(1).

9. Clone the next child of node 1, which is node 4:

   • A new node, newNode(4), is created with the value 4.
   • Node 4 has no children, so the recursion ends here for this branch. newNode(4) is added to the children list of newNode(1).

10. Clone the next child of node 1, which is node 5:

    • A new node, newNode(5), is created with the value 5.
    • Node 5 has no children, so the recursion ends here for this branch. newNode(5) is added to the children list of newNode(1).

11. Finish cloning the entire tree:

    • The cloned root node newNode(1) now has four children: newNode(2), newNode(3), newNode(4), and newNode(5).
    • Each cloned child has the same structure and values as the original tree, but no references are shared between the original and cloned trees.

Code

import java.util.ArrayList;
import java.util.List;

// class NAryNode {
//     public int val; // Value of the current node
//     public List<NAryNode> children; // List of children for the current node

//     // Constructor to initialize a node with a value
//     public NAryNode(int val) {
//         this.val = val;
//         this.children = new ArrayList<>();
//     }
// }

public class Solution {
    // Method to clone the N-ary tree
    public NAryNode cloneTree(NAryNode root) {
        // Base case: if the current node is null, return null
        if (root == null) return null;

        // Create a new node with the same value as the root node
        NAryNode newNode = new NAryNode(root.val);

        // Recursively clone all the children of the current node
        for (NAryNode child : root.children) {
            newNode.children.add(cloneTree(child));
        }

        // Return the new node, which represents the root of the cloned subtree
        return newNode;
    }

    // Helper method to print the N-ary tree in level order
    public void printTree(NAryNode root) {
        // Base case: if the tree is empty, return
        if (root == null) return;

        // Initialize a list to store nodes at the current level
        List<NAryNode> currentLevel = new ArrayList<>();
        currentLevel.add(root);

        // Process all levels of the tree
        while (!currentLevel.isEmpty()) {
            List<NAryNode> nextLevel = new ArrayList<>();
            
            // Print all nodes at the current level
            for (NAryNode node : currentLevel) {
                System.out.print(node.val + " "); // Print the value of the current node
                
                // Add children of the current node to the next level list
                for (NAryNode child : node.children) {
                    nextLevel.add(child);
                }
            }
            
            System.out.println(); // Move to the next line for the next level

            // Move to the next level
            currentLevel = nextLevel;
        }
    }

    public static void main(String[] args) {
        // Create the original N-ary tree for Example 1
        NAryNode root1 = new NAryNode(1);
        root1.children.add(new NAryNode(2));
        root1.children.add(new NAryNode(3));
        root1.children.add(new NAryNode(4));
        root1.children.get(1).children.add(new NAryNode(5));
        root1.children.get(1).children.add(new NAryNode(6));

        Solution solution = new Solution();

        // Clone the tree using the cloneTree method
        NAryNode clonedRoot1 = solution.cloneTree(root1);

        // Print the original tree
        System.out.println("Original Tree:");
        solution.printTree(root1);

        // Print the cloned tree
        System.out.println("\nCloned Tree:");
        solution.printTree(clonedRoot1);
    }
}

Complexity Analysis

Time Complexity

• The time complexity of the cloneTree method is , where n is the total number of nodes in the N-ary tree.
• This is because each node is visited exactly once during the cloning process, and for each node, we perform a constant amount of work (creating a new node and cloning its children).

Space Complexity

• The space complexity is due to the space required for the recursion stack. In the worst case, the tree is skewed, and the depth of the recursion can be equal to the total number of nodes. In the best case, for a balanced tree, the depth of recursion is .
• Additionally, a new tree with n nodes is created, requiring extra space.