medium Clone Binary Tree With Random Pointer

Problem Statement

You are given a binary tree where each node has an additional pointer called the random pointer. This random pointer may point to any other node in the tree or could be set to null.

Create and return a deep copy of this binary tree.

In the input, each node is represented by a pair [val, random_index]:

• val is an integer that represents the value of the node.
• random_index is the index of the node (in the input list) to which the random pointer is pointing, or null if it does not point to any node.

The deep copy must replicate both the structure of the tree and the configuration of the random pointers.

Examples

Example 1:

• Input: root = [[3, 1], [9, null], [20, 0], [15, 2], [7, null]]

• Expected Output: [[3, 1], [9, null], [20, 0], [15, 2], [7, null]]
• Justification: The output is a deep copy of the original tree.

Example 2:

• Input: [[5, 4], [12, 0], [7, null], [2, 1], [9, 3]]

• Expected Output: [[5, 4], [12, 0], [7, null], [2, 1], [9, 3]]
• Justification: The output is a deep copy of the original tree.

Example 3:

• Input: root = [[1, 2], [4, null], [3, 0], [2, 1], [6, null]]
• Expected Output: [[1, 2], [4, null], [3, 0], [2, 1], [6, null]]
• Justification: The output is a deep copy of the original tree.

Constraints:

• The number of nodes in the tree is in the range [0, 1000].
• 1 <= Node.val <= 10⁶

Solution

To solve the problem of cloning a binary tree where each node has an additional random pointer, we use a combination of recursion and a hash map to efficiently create a deep copy. The hash map keeps track of each original node and its corresponding cloned node, which helps us manage the random pointers. The recursive approach ensures that we visit each node exactly once, making a copy and assigning left, right, and random pointers correctly.

The solution begins by checking if the input tree is empty. If so, it returns null since there is nothing to copy. For non-empty trees, the solution initiates the cloning process from the root. It recursively traverses the original tree, copying nodes while maintaining their connections. The hash map helps to quickly find cloned nodes whenever they are needed, especially for handling the random pointers.

Step-by-Step Algorithm

1. Check if the root is null:

   • If the input tree is empty (root == null), return null because there is no tree to clone.

2. Initialize a HashMap:

   • Create a HashMap<Node, Node> called clonedMap to store the mapping of each original node to its corresponding cloned node.
   • This map helps to quickly access the cloned version of a node when needed, especially for handling random pointers.

3. Start cloning the tree from the root node:

   • Call the recursive function cloneNode with the root node and the clonedMap.
   • The cloneNode function will handle the cloning process for each node recursively.

4. In the cloneNode function:

   • Base Case: If the input node is null, return null because there is nothing to clone.
   • Check for Existing Cloned Node: If the input node has already been cloned (i.e., it is present in clonedMap), return the corresponding cloned node from the map.
   • Clone the Current Node:
     • Create a new Node instance (newNode) as a copy of the original node (with the same value).
     • Store the mapping between the original node and the new cloned node in the clonedMap.
   • Recursively Clone the Children:
     • Call cloneNode recursively for the left and right children of the original node.
     • Assign the returned cloned left and right children to the left and right pointers of newNode.
   • Recursively Clone the Random Pointer:
     • Call cloneNode recursively for the random pointer of the original node.
     • Assign the returned cloned node to the random pointer of newNode.
   • Return the Cloned Node: Return the cloned node (newNode) after its children and random pointers are set.

5. Return the Cloned Root Node:

   • After completing the recursive cloning process, return the result of cloneNode(root) as the cloned root of the entire tree.

Algorithm Walkthrough

Input: [[3, 1], [9, null], [20, 0], [15, 2], [7, null]]:

1. Initial Function Call:

   • Call copyRandomBinaryTree(root) with root being the node with value 3.
   • Initialize clonedMap as an empty HashMap<Node, Node>.

2. Start Cloning from Root (Node 3):

   • Call cloneNode(3).
   • Since Node 3 is not null and not in clonedMap, create a new node newNode with value 3.
   • Add the mapping 3 -> newNode to clonedMap.

3. Recursively Clone Left Child (Node 9):

   • Call cloneNode(9).
   • Since Node 9 is not null and not in clonedMap, create a new node newNode with value 9.
   • Add the mapping 9 -> newNode to clonedMap.

4. Recursively Clone Left Child of Node 9 (Node 15):

   • Call cloneNode(15).
   • Since Node 15 is not null and not in clonedMap, create a new node newNode with value 15.
   • Add the mapping 15 -> newNode to clonedMap.
   • Node 15 has no children, so recursive calls cloneNode(null) for both left and right children return null.
   • Assign null to newNode.left and newNode.right.
   • Node 15's random pointer points to Node 20. Since Node 20 is not yet cloned, recursively call cloneNode(20) to clone it.

5. Recursively Clone Node 20 (from Node 15's random pointer):

   • Call cloneNode(20).
   • Since Node 20 is not null and not in clonedMap, create a new node newNode with value 20.
   • Add the mapping 20 -> newNode to clonedMap.
   • Node 20 has no children, so recursive calls cloneNode(null) for both left and right children return null.
   • Assign null to newNode.left and newNode.right.
   • Node 20's random pointer points to Node 3. Since Node 3 is already cloned, use clonedMap to find its clone and set it as newNode.random.
   • Return the cloned node newNode for Node 20.

6. Finish Cloning Node 15:

   • Node 15's random pointer now correctly points to the cloned Node 20.
   • Return the cloned node newNode for Node 15.

7. Recursively Clone Right Child of Node 9 (Node 7):

   • Call cloneNode(7).
   • Since Node 7 is not null and not in clonedMap, create a new node newNode with value 7.
   • Add the mapping 7 -> newNode to clonedMap.
   • Node 7 has no children, so recursive calls cloneNode(null) for both left and right children return null.
   • Assign null to newNode.left and newNode.right.
   • Node 7 has no random pointer (random = null), so the recursive call cloneNode(null) for the random pointer returns null.
   • Assign null to newNode.random.
   • Return the cloned node newNode for Node 7.

8. Finish Cloning Node 9:

   • Assign the cloned nodes for 9's left and right children (15 and 7) to newNode.left and newNode.right.
   • Node 9 has no random pointer (random = null), so newNode.random remains null.
   • Return the cloned node newNode for Node 9.

9. Recursively Clone Right Child of Root Node 3 (Node 20):

   • Node 20 has already been cloned when cloning Node 15's random pointer.
   • Retrieve the cloned node for 20 from clonedMap.

10. Finish Cloning Root Node 3:

    • Assign the cloned nodes for 3's left and right children (9 and 20) to newNode.left and newNode.right.
    • Node 3's random pointer points to Node 9. Since Node 9 is already cloned, use clonedMap to find its clone and set it as newNode.random.
    • Return the cloned root node newNode.

11. Final Output:

    • The cloned tree is returned with the correct structure and all random pointers replicated exactly as in the original tree.

Code

import java.util.HashMap;

// TreeNode class definition with value, left, right, and random pointers
// class TreeNode {
//     public int val;
//     public TreeNode left;
//     public TreeNode right;
//     public TreeNode random;

//     // Constructor to initialize a TreeNode with a given value
//     public TreeNode(int val) {
//         this.val = val;
//         this.left = null;
//         this.right = null;
//         this.random = null;
//     }
// }

class Solution {

  // Method to deep copy the binary tree with random pointers
  public TreeNode copyRandomBinaryTree(TreeNode root) {
    // If the original tree is empty, return null
    if (root == null) return null;

    // HashMap to store the mapping of original nodes to their cloned counterparts
    HashMap<TreeNode, TreeNode> clonedMap = new HashMap<>();

    // Start the cloning process from the root
    return cloneNode(root, clonedMap);
  }

  // Helper method to clone a given node
  private TreeNode cloneNode(
    TreeNode node,
    HashMap<TreeNode, TreeNode> clonedMap
  ) {
    // Base case: If the node is null, return null
    if (node == null) return null;

    // If the node has already been cloned, return the cloned node from the map
    if (clonedMap.containsKey(node)) return clonedMap.get(node);

    // Create a new node as a deep copy of the original node
    TreeNode newNode = new TreeNode(node.val);

    // Add the new cloned node to the map
    clonedMap.put(node, newNode);

    // Recursively clone the left and right children and assign them to the cloned node
    newNode.left = cloneNode(node.left, clonedMap);
    newNode.right = cloneNode(node.right, clonedMap);

    // Recursively clone the random pointer and assign it to the cloned node
    newNode.random = cloneNode(node.random, clonedMap);

    // Return the cloned node
    return newNode;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Creating the original tree for Example 1
    TreeNode root = new TreeNode(3);
    root.left = new TreeNode(9);
    root.right = new TreeNode(20);
    root.right.left = new TreeNode(15);
    root.right.right = new TreeNode(7);

    // Setting up random pointers
    root.random = root.left;
    root.left.random = null;
    root.right.random = root;
    root.right.left.random = root.right;
    root.right.right.random = null;

    // Cloning the binary tree
    TreeNode clonedRoot = solution.copyRandomBinaryTree(root);

    // Printing the original tree nodes
    System.out.println("Original Tree:");
    printNodeDetails(root, "root");
    printNodeDetails(root.left, "root.left");
    printNodeDetails(root.right, "root.right");
    printNodeDetails(root.right.left, "root.right.left");
    printNodeDetails(root.right.right, "root.right.right");

    // Printing the cloned tree nodes
    System.out.println("\nCloned Tree:");
    printNodeDetails(clonedRoot, "clonedRoot");
    printNodeDetails(clonedRoot.left, "clonedRoot.left");
    printNodeDetails(clonedRoot.right, "clonedRoot.right");
    printNodeDetails(clonedRoot.right.left, "clonedRoot.right.left");
    printNodeDetails(clonedRoot.right.right, "clonedRoot.right.right");
  }

  // Helper method to print detailed node information
  private static void printNodeDetails(TreeNode node, String nodeName) {
    if (node == null) return;
    System.out.println(
      nodeName +
        ".val = " +
        node.val +
        ", " +
        nodeName +
        ".random = " +
        (node.random != null ? node.random.val : "null")
    );
  }
}

Complexity Analysis

Time Complexity

The time complexity of the solution is , where N is the number of nodes in the binary tree. This is because we are visiting each node exactly once to create a copy of it, and then processing its left, right, and random pointers.

The hash map operations (inserting and looking up nodes) are on average due to its constant time complexity for these operations.

Space Complexity

The space complexity is as well. This is because we use a hash map to store the mapping between each original node and its cloned node.

Additionally, the recursive stack can also go up to in the worst case (for example, in the case of a completely unbalanced tree).