1485. Clone Binary Tree With Random Pointer

MediumTreeDepth-First SearchBreadth-First SearchHash TableBinary Tree
Leetcode Link

Problem Description

In this LeetCode problem, we are given a binary tree where each node has an additional feature. Along with the usual left and right child pointers, each node also contains a random pointer. The random pointer can point to any node in the tree or be null.

The task is to create a deep copy of this binary tree. A deep copy means that we need to create a new binary tree that looks exactly like the original tree, but is completely independent of the original. Changes to the new tree should not affect the old one and vice versa. The new nodes' random pointers should point to the corresponding nodes in the copied tree, not the original tree.

Each node in the tree is represented as a pair [val, random_index] where:

  • val represents the value of the node.
  • random_index is the index of the node to which the random pointer points, or null if the random pointer does not point to any node.

Lastly, the output should be provided using the NodeCopy class, which is essentially a clone of the Node class with identical attributes and constructors.

Intuition

To solve this problem, we need to traverse the original tree and create a new copy of each node along the way. This process is typically done using depth-first search (DFS). However, directly copying the random pointers is complicated because the node that a random pointer refers to might not have been copied yet. This means we can't simply set the new node's random pointer during the initial traversal.

The intuition behind the solution is to use a hashmap (a dictionary in Python) to store the mapping from original nodes to their respective copies. This way, we can set the random pointer at any time during the traversal by looking up the corresponding node in the hashmap.

The algorithm works as follows:

  1. Start at the root of the original tree.
  2. If the current node is null, return null, as there's nothing to copy.
  3. If the current node's copy already exists in the hashmap, return the copy to avoid duplication.
  4. If the copy does not exist yet, create a new NodeCopy instance with the same value.
  5. Store the new NodeCopy instance in the hashmap, with the original node as the key.
  6. Set the left and right child pointers for the NodeCopy by recursively calling our DFS function.
  7. Set the random pointer for the NodeCopy in a similar fashion, by calling DFS for the original node's random pointer and using the hashmap for reference.
  8. After the recursion completes, return the copy of the root node which now represents the root of the deep-copied tree.

By using a hashmap to maintain a correspondence between the original nodes and the copied nodes, we ensure that the random pointers get correctly assigned even if the target nodes are copied later during the DFS traversal.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Solution Approach

The implementation of the proposed solution approach uses Depth-First Search (DFS) as its core algorithm to traverse and copy the tree. The DFS algorithm is preferred because it allows us to systematically visit and clone every node in the tree while maintaining the structure, including the random pointers.

Here's a step-by-step breakdown of how the solution is implemented:

  1. Function Definition and Entry Point:

    • A method named copyRandomBinaryTree is defined, which takes the root of the binary tree as its argument.
    • This method initializes a hashmap mp which is used to map original nodes to their corresponding copied nodes, and calls the dfs recursive helper function with the original root as the parameter.

  2. Recursive DFS Function:

    • The dfs function is defined to recursively traverse and create copies of nodes.
    • If the current node is None, dfs returns None, indicating there is no node to copy.

  3. HashMap Usage:

    • If the current node has already been copied, meaning it exists in the mp hashmap, dfs returns the copy from the hashmap directly.
    • This ensures that each original node is copied exactly once, and the already created copies can be reused whenever needed.

  4. Node Copying:

    • If a node hasn't been copied yet, a new NodeCopy instance is created with the same value as the original node.
    • This new copy is stored in mp using the original node as the key.

  5. Recursively Setting Pointers:

    • The left and right child pointers of the newly created NodeCopy instance are set by recursively calling the dfs function with the original node's left and right children, respectively.
    • Similarly, the random pointer for the NodeCopy is set by recursively calling the dfs function with the original node's random pointer as the argument.

  6. Returning the Deep Copy:

    • Once all pointers for a node are set, the dfs function returns the NodeCopy instance.
    • This process continues until all nodes in the original tree have been visited and the entire structure including the random pointers is recreated in the copied tree.

  7. Result:

    • The copyRandomBinaryTree method finally returns the copied root node, which represents the starting point of the newly created deep copy of the tree.

Given the importance of maintaining the integrity of the random pointers, the use of the hashmap is essential. It acts as a link between original nodes and their copies, allowing the algorithm to set the random pointers correctly without needing the entire tree to be copied beforehand.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Example Walkthrough

Let's walk through the solution approach with an example.

Suppose we have the following binary tree, where R represents the random pointer:

1     1
2   /   \
3  2     3
4 / \   / R
54   5 6   7

And let's arbitrarily assign random pointers as follows:

  • Node 1's random pointer points to 3
  • Node 2's random pointer points to 4
  • Node 3's random pointer points to 7
  • Other random pointers are null

Step 1: Call copyRandomBinaryTree with the root node (node 1).

Step 2: Since node 1 is not None and does not exist in the hashmap yet, create a new NodeCopy instance for node 1 named copy1 and add it to the hashmap with the original node 1 as the key.

Step 3: Recursively call dfs on node 1's left child (node 2).

  • Since node 2 is newly encountered, create a NodeCopy instance for it named copy2 and add it to the hashmap.
  • Recursively set the left and right child pointers for copy2 by calling dfs on node 2's children.
  • Set the random pointer for copy2 by using the hashmap and the random pointer of node 2, which points to node 4.

Step 4: Similarly, recurse on the right child of node 1 (node 3).

  • Create a NodeCopy instance for node 3, named copy3.
  • Since node 3's random pointer points to node 7, we ensure that the dfs function is called on node 7, creating a new NodeCopy instance named copy7 and then using the hashmap to set the random pointer for copy3.
  • Recursively set the left and right children for copy3 in the same manner.

Step 5: Continue recursion for all nodes following the same pattern, creating NodeCopy instances (copy4, copy5, copy6) as the recursion unfolds, and adding them to the hashmap.

Step 6: Once the dfs has processed all nodes, the recursion starts resolving, and the pointers of already created NodeCopy instances are set according to the original tree's structure and random pointers.

Step 7: Ultimately, the copyRandomBinaryTree method returns copy1, which is the root of the deep-copied tree that mirrors the structure and random pointers of the original tree.

This step-by-step process allows the algorithm to deep copy each node, maintain child structure, and appropriately set random pointers without confusion or error. The resulting deep copy is a binary tree in which each NodeCopy is equivalent to its counterpart in the original tree, with the random pointers correctly assigned according to the new tree's structure.

Solution Implementation

1# Definition for a Node with an additional random pointer.
2class Node:
3    def __init__(self, val=0, left=None, right=None, random=None):
4        self.val = val
5        self.left = left
6        self.right = right
7        self.random = random
8
9
10# Definition for a NodeCopy, which is used to represent the cloned tree.
11class NodeCopy:
12    def __init__(self, val=0, left=None, right=None, random=None):
13        self.val = val
14        self.left = left
15        self.right = right
16        self.random = random
17
18
19class Solution:
20    def copyRandomBinaryTree(self, root: 'Optional[Node]') -> 'Optional[NodeCopy]':
21        # Helper function to perform a deep copy of the tree using DFS
22        def dfs_clone(node):
23            # Base case: If the current node is None, return None
24            if node is None:
25                return None
26          
27            # If we have already cloned this node, return its clone from the map
28            if node in clone_map:
29                return clone_map[node]
30          
31            # Create a new NodeCopy for the current node
32            cloned_node = NodeCopy(node.val)
33          
34            # Save this cloned node in the map with the original node as the key
35            clone_map[node] = cloned_node
36          
37            # Recursively clone the left subtree
38            cloned_node.left = dfs_clone(node.left)
39          
40            # Recursively clone the right subtree
41            cloned_node.right = dfs_clone(node.right)
42          
43            # Recursively clone the random pointer
44            cloned_node.random = dfs_clone(node.random)
45          
46            # Return the cloned node
47            return cloned_node
48      
49        # Initialize a map to keep track of original node to its cloned counterpart
50        clone_map = {}
51      
52        # Kick off the cloning process starting from the root of the tree
53        return dfs_clone(root)
54
1/**
2 * Definition for a Node with a random pointer.
3 * public class Node {
4 *     int val; // The value of the node
5 *     Node left; // Reference to the left child
6 *     Node right; // Reference to the right child
7 *     Node random; // Reference to a random node
8 *     Node() {} // Default constructor
9 *     Node(int val) { this.val = val; } // Constructor with node value
10 *     Node(int val, Node left, Node right, Node random) { // Constructor with all properties
11 *         this.val = val;
12 *         this.left = left;
13 *         this.right = right;
14 *         this.random = random;
15 *     }
16 * }
17 */
18
19class Solution {
20    private Map<Node, NodeCopy> nodeMap; // Map to store original nodes to their copied nodes
21
22    public NodeCopy copyRandomBinaryTree(Node root) {
23        nodeMap = new HashMap<>(); // Initialize the hashmap
24        return clone(root); // Begin recursion to clone the tree starting with the root
25    }
26
27    // Helper method to perform a deep copy of the tree using DFS
28    private NodeCopy clone(Node node) {
29        if (node == null) {
30            return null; // Base case: If the node is null, return null
31        }
32
33        // If we have already created a copy of the current node, return its copy
34        if (nodeMap.containsKey(node)) {
35            return nodeMap.get(node);
36        }
37
38        // Create a new copy for the current node
39        NodeCopy nodeCopy = new NodeCopy(node.val);
40        nodeMap.put(node, nodeCopy); // Add the original and its copy to the map
41
42        // Recursively clone the left and right subtrees
43        nodeCopy.left = clone(node.left);
44        nodeCopy.right = clone(node.right);
45
46        // Recursively clone the random node
47        nodeCopy.random = clone(node.random);
48
49        // Return the copied node
50        return nodeCopy;
51    }
52}
53
54/**
55 * Definition for the copy of a node which does not have random and child pointers initialized.
56 */
57class NodeCopy {
58    int val; // Node value
59    NodeCopy left; // Reference to the left child
60    NodeCopy right; // Reference to the right child
61    NodeCopy random; // Reference to a random node
62    NodeCopy() {} // Default constructor
63    NodeCopy(int val) { this.val = val; } // Constructor with node value
64}
65
1// Definition for a Node of a binary tree with an additional pointer to a random node.
2struct Node {
3    int val; // Value contained in the node
4    Node *left; // Pointer to left child
5    Node *right; // Pointer to right child
6    Node *random; // Pointer to a random node, which could be any node in the tree or null
7    Node() : val(0), left(nullptr), right(nullptr), random(nullptr) {}
8    Node(int x) : val(x), left(nullptr), right(nullptr), random(nullptr) {}
9    Node(int x, Node *left, Node *right, Node *random) : val(x), left(left), right(right), random(random) {}
10};
11
12// The NodeCopy structure parallels the Node structure but for the cloned tree.
13struct NodeCopy {
14    int val;
15    NodeCopy *left;
16    NodeCopy *right;
17    NodeCopy *random;
18    NodeCopy(int x) : val(x), left(nullptr), right(nullptr), random(nullptr) {}
19};
20
21class Solution {
22public:
23    // Main function to copy a random binary tree.
24    NodeCopy* copyRandomBinaryTree(Node* root) {
25        unordered_map<Node*, NodeCopy*> mapping; // Map original nodes to their copies
26        return cloneTree(root, mapping);
27    }
28
29    // Helper function to recursively clone the tree, including the random pointers.
30    NodeCopy* cloneTree(Node* node, unordered_map<Node*, NodeCopy*>& mapping) {
31        if (!node) { // Base case: if current node is null, return null
32            return nullptr;
33        }
34      
35        if (mapping.count(node)) { // Check if the node is already cloned
36            return mapping[node]; // Return the cloned node
37        }
38      
39        // Create a new copy for the current node
40        NodeCopy* clone = new NodeCopy(node->val);
41      
42        // Save the mapping from the original node to the cloned node
43        mapping[node] = clone;
44      
45        // Recursively clone the left subtree
46        clone->left = cloneTree(node->left, mapping);
47      
48        // Recursively clone the right subtree
49        clone->right = cloneTree(node->right, mapping);
50      
51        // Recursively clone the random pointer
52        clone->random = cloneTree(node->random, mapping);
53      
54        // Return the cloned node
55        return clone;
56    }
57};
58
1// Node represents a node in a binary tree with an additional random pointer.
2interface Node {
3    val: number; // Value contained in the node
4    left: Node | null; // Pointer to left child
5    right: Node | null; // Pointer to right child
6    random: Node | null; // Pointer to a random node, which could be any node in the tree or null
7}
8
9// NodeCopy represents a node in the cloned binary tree with an additional random pointer.
10interface NodeCopy {
11    val: number; // Value contained in the node
12    left: NodeCopy | null; // Pointer to left child
13    right: NodeCopy | null; // Pointer to right child
14    random: NodeCopy | null; // Pointer to a random node, which could be any node in the cloned tree or null
15}
16
17// mapping stores a correspondence between nodes of the original tree and the cloned tree.
18const mapping = new Map<Node, NodeCopy>();
19
20// copyRandomBinaryTree creates a deep copy of a binary tree, including the random pointers.
21function copyRandomBinaryTree(root: Node | null): NodeCopy | null {
22    return cloneTree(root, mapping);
23}
24
25// cloneTree recursively clones the tree, including the random pointers.
26function cloneTree(node: Node | null, mapping: Map<Node, NodeCopy>): NodeCopy | null {
27    if (node === null) { // Base case: if current node is null, return null
28        return null;
29    }
30
31    if (mapping.has(node)) { // Check if the node is already cloned
32        return mapping.get(node)!; // Return the cloned node
33    }
34
35    // Create a new copy for the current node
36    const clone = { val: node.val, left: null, right: null, random: null } as NodeCopy;
37
38    // Save the mapping from the original node to the cloned node
39    mapping.set(node, clone);
40
41    // Recursively clone the left and right subtrees
42    clone.left = cloneTree(node.left, mapping);
43    clone.right = cloneTree(node.right, mapping);
44  
45    // Recursively clone the random pointer
46    // We delay setting the random property to ensure all potential nodes have been visited and cloned first,
47    // which is necessary because the random property can point to nodes not yet visited in a depth-first search.
48    clone.random = cloneTree(node.random, mapping);
49
50    // Return the cloned node
51    return clone;
52}
53
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Time and Space Complexity

Time Complexity

The time complexity of the copyRandomBinaryTree function is O(N), where N is the number of nodes in the binary tree. This is because the function uses a depth-first search (DFS) approach to traverse each node exactly once. Even with the additional random pointer, each node and its random pointer are accessed a constant number of times.

Here's how the time is spent:

  • Each node is visited exactly once due to the memoization (storing in the mp dictionary). This prevents redundant visits to the same node.
  • For each node, constant-time operations are performed (creating a node copy, assigning left and right children, and assigning the random pointer).
  • Thus, the time complexity is directly proportional to the number of nodes.

Space Complexity

The space complexity of the copyRandomBinaryTree function is also O(N). The reasoning is as follows:

  • O(N) space for the mp dictionary, which holds a reference for each node in the original binary tree.
  • O(H) space for the call stack used during the DFS traversal, where H is the height of the tree. In the worst case (a skewed tree), this could be O(N), but for a balanced tree, it would be O(log N).
  • Since it's possible that the stack space (recursive calls) and the space for the new tree could both reach O(N) in the worst case, we consider the worst-case scenario.

Combining both considerations, the overall space complexity remains O(N) due to the space required for the new tree and the call stack during recursion.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search can be used to find whether two components in a graph are connected.

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ