1485. Clone Binary Tree With Random Pointer
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.
Flowchart Walkthrough
To determine the suitable algorithm for the problem presented in Leetcode 1485. Clone Binary Tree With Random Pointer, we'll apply the algorithm decision-making process using the Flowchart. Follow along with this step-by-step analysis:
Is it a graph?
- Yes: Even though the structure is basically a binary tree, the presence of a random pointer alters the typical tree structure, making it similar to a graph because the random pointer can point to any node in the tree, forming unpredictable connections.
Is it a tree?
- Yes: Despite the added complexity of the random pointer, the primary data structure is still a tree (binary tree).
Using DFS:
- The decision focuses here for trees. DFS is particularly effective as it helps explore each node and its random pointer, facilitating the cloning process. Depth-First Search allows us to traverse the tree deeply from root to leaves, dealing correctly with both the child and random pointers by cloning nodes and maintaining their relationships.
Conclusion: The flowchart leads to using the DFS algorithm, ideal for traversing and cloning elements in a tree structure, especially when special care must be taken to correctly reproduce the topology of a tree with additional randomly connected nodes.
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:
- Start at the root of the original tree.
- If the current node is null, return null, as there's nothing to copy.
- If the current node's copy already exists in the hashmap, return the copy to avoid duplication.
- If the copy does not exist yet, create a new
NodeCopy
instance with the same value. - Store the new
NodeCopy
instance in the hashmap, with the original node as the key. - Set the left and right child pointers for the
NodeCopy
by recursively calling our DFS function. - 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. - 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.
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:
-
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 thedfs
recursive helper function with the original root as the parameter.
- A method named
-
Recursive DFS Function:
- The
dfs
function is defined to recursively traverse and create copies of nodes. - If the current node is
None
,dfs
returnsNone
, indicating there is no node to copy.
- The
-
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.
- If the current node has already been copied, meaning it exists in the
-
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.
- If a node hasn't been copied yet, a new
-
Recursively Setting Pointers:
- The left and right child pointers of the newly created
NodeCopy
instance are set by recursively calling thedfs
function with the original node's left and right children, respectively. - Similarly, the random pointer for the
NodeCopy
is set by recursively calling thedfs
function with the original node's random pointer as the argument.
- The left and right child pointers of the newly created
-
Returning the Deep Copy:
- Once all pointers for a node are set, the
dfs
function returns theNodeCopy
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.
- Once all pointers for a node are set, the
-
Result:
- The
copyRandomBinaryTree
method finally returns the copied root node, which represents the starting point of the newly created deep copy of the tree.
- The
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 to3
- Node
2
's random pointer points to4
- Node
3
's random pointer points to7
- 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 aNodeCopy
instance for it namedcopy2
and add it to the hashmap. - Recursively set the left and right child pointers for
copy2
by callingdfs
on node2
's children. - Set the random pointer for
copy2
by using the hashmap and the random pointer of node2
, which points to node4
.
Step 4: Similarly, recurse on the right child of node 1
(node 3
).
- Create a
NodeCopy
instance for node3
, namedcopy3
. - Since node
3
's random pointer points to node7
, we ensure that thedfs
function is called on node7
, creating a newNodeCopy
instance namedcopy7
and then using the hashmap to set the random pointer forcopy3
. - 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
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 themp
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, whereH
is the height of the tree. In the worst case (a skewed tree), this could beO(N)
, but for a balanced tree, it would beO(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.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
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
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
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 Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.