Problem Description

You are given a binary tree where each node has an extra pointer called random that can point to any node in the tree or be null. Your task is to create a complete deep copy of this tree.

A deep copy means creating an entirely new tree with new nodes that have the same structure and values as the original tree. The new tree should preserve:

• The same binary tree structure (left and right child relationships)
• The same node values
• The same random pointer connections (but pointing to nodes in the new tree, not the original)

The tree nodes have four attributes:

• val: the integer value stored in the node
• left: pointer to the left child
• right: pointer to the right child
• random: pointer to any node in the tree (or null)

The solution uses a depth-first search (DFS) approach with memoization. It maintains a hash map mp to store the mapping between original nodes and their copies. This prevents creating duplicate copies of the same node and ensures that random pointers correctly reference nodes in the new tree.

The algorithm works as follows:

1. If the current node is null, return null
2. If the node has already been copied (exists in the hash map), return the existing copy
3. Create a new copy node with the same value
4. Store the mapping in the hash map
5. Recursively copy the left child, right child, and random pointer target
6. Return the copied node

This approach handles the challenge of the random pointers potentially creating cycles or pointing to nodes that haven't been created yet by using the hash map to track all created copies.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: While this is specifically a binary tree problem, a tree is a special type of graph (an acyclic connected graph). Additionally, the random pointers can create arbitrary connections between nodes, making this graph-like in nature.

Is it a tree?

• Yes: The base structure is explicitly a binary tree with left and right child pointers. Even though we have additional random pointers, the fundamental structure remains a tree.

DFS

• Yes: We arrive at DFS as our solution approach.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this problem.

Why DFS is the Right Choice

The DFS pattern is particularly well-suited for this problem because:

1. Tree Traversal: DFS naturally traverses tree structures by exploring each branch completely before backtracking.

2. Handling Random Pointers: The random pointers can point to any node in the tree, including nodes that haven't been visited yet or nodes that have already been processed. DFS with memoization elegantly handles this by:

   • Creating nodes on first encounter
   • Returning existing copies from the hash map on subsequent encounters
   • Preventing infinite recursion if cycles exist through random pointers

3. Deep Copy Requirements: DFS allows us to recursively create the entire structure, ensuring all connections (left, right, and random) are properly established in the new tree.

4. Memoization Integration: The recursive nature of DFS works perfectly with a hash map to track already-copied nodes, which is essential when dealing with the random pointers that could create complex reference patterns.

Intuition

When we need to create a deep copy of a data structure, the natural approach is to traverse it and create new nodes as we go. For a regular binary tree, this would be straightforward - we'd recursively copy each node and its children. However, the random pointers add a significant complication.

The key challenge is that a random pointer might point to:

• A node we haven't visited yet (deeper in the tree)
• A node we've already copied (an ancestor or a node in another branch)
• Null

If we try to naively follow and copy every pointer, we might end up creating duplicate copies of the same node, or worse, get stuck in infinite recursion if there are cycles through the random pointers.

The breakthrough insight is to treat this as a graph traversal problem where we need to visit each node exactly once. We need a way to remember which nodes we've already copied. This naturally leads us to use a hash map that maps original nodes to their copies.

Think of it like this: imagine you're duplicating a complex network of roads (the tree) where some roads have special tunnels (random pointers) that can connect to any other road. As you build your duplicate network, you need a registry to track which roads you've already built. When you encounter a tunnel, you check your registry:

• If the destination road already exists in your new network, connect to it
• If it doesn't exist yet, build it now and add it to your registry
• This ensures every road is built exactly once, regardless of how many tunnels lead to it

The DFS approach emerges naturally because we need to fully explore each path - including the random pointer - before moving on. By checking our hash map first before creating any node, we ensure that each node in the original tree gets exactly one corresponding node in the copied tree, preserving all the complex interconnections created by the random pointers.

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

Solution Approach

The implementation uses a recursive DFS approach with memoization to handle the deep copy. Let's walk through the key components:

Data Structure:

• Hash map mp: Maps original nodes to their corresponding copied nodes. This serves as our memoization table and prevents duplicate copies.

The DFS Function:

The core logic is encapsulated in the dfs helper function that handles four main cases:

1. Base Case - Null Node:

   if root is None:
       return None

   If we encounter a null pointer (whether from left, right, or random), we simply return None.

2. Memoization Check:

   if root in mp:
       return mp[root]

   Before creating a new copy, we check if this node has already been copied. If it exists in our hash map, we return the existing copy. This is crucial for handling random pointers that might point to already-processed nodes.

3. Node Creation and Caching:

   copy = NodeCopy(root.val)
   mp[root] = copy

   We create a new node with the same value as the original and immediately store it in our hash map. This is done BEFORE recursively processing children to handle potential cycles through random pointers.

4. Recursive Copying:

   copy.left = dfs(root.left)
   copy.right = dfs(root.right)
   copy.random = dfs(root.random)

   We recursively process all three pointers. The beauty of this approach is that we treat all pointers uniformly - the dfs function doesn't need to know whether it's processing a tree edge or a random pointer.

Why This Order Matters:

The algorithm strategically creates and caches the node before processing its pointers. This prevents infinite recursion in cases where:

• A node's random pointer points to itself
• Multiple nodes have random pointers creating a cycle
• A child's random pointer points back to an ancestor

Time and Space Complexity:

• Time: O(n) where n is the number of nodes, as each node is visited exactly once
• Space: O(n) for the hash map and the recursion stack in the worst case (skewed tree)

The elegance of this solution lies in its simplicity - by treating the structure as a graph and using memoization, we handle all the complex cases of random pointers without any special logic.

Example Walkthrough

Let's walk through a small example to illustrate how the solution handles the deep copy with random pointers.

Original Tree:

      1 (random → 3)
     / \
    2   3 (random → 2)
        (random → null)

Step-by-step execution:

1. Start with root (node 1):

   • Check hash map: empty, node 1 not found
   • Create new node with value 1: copy1 = NodeCopy(1)
   • Store in hash map: mp[node1] = copy1
   • Process left child (node 2)

2. Process node 2:

   • Check hash map: node 2 not found
   • Create new node: copy2 = NodeCopy(2)
   • Store in hash map: mp[node2] = copy2
   • Process left child: null, return None
   • Process right child: null, return None
   • Process random: null, return None
   • Return copy2 to parent

3. Back to node 1, process right child (node 3):

   • Check hash map: node 3 not found
   • Create new node: copy3 = NodeCopy(3)
   • Store in hash map: mp[node3] = copy3
   • Process left child: null, return None
   • Process right child: null, return None
   • Process random (points to node 2):
     • Check hash map: node 2 found! Return existing copy2
   • Set copy3.random = copy2
   • Return copy3 to parent

4. Back to node 1, process random (points to node 3):

   • Check hash map: node 3 found! Return existing copy3
   • Set copy1.random = copy3

5. Complete the connections:

   • copy1.left = copy2
   • copy1.right = copy3
   • Return copy1 as the root of the copied tree

Final Copied Tree:

     copy1 (random → copy3)
     /    \
  copy2    copy3 (random → copy2)
  (random → null)

Key Observations:

• When node 3's random pointer needed node 2, it was already in the hash map, so we reused the existing copy
• When node 1's random pointer needed node 3, it had just been created and cached, preventing duplicate creation
• The hash map ensures each original node maps to exactly one copied node, preserving the structure perfectly

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary tree.

The algorithm performs a depth-first search (DFS) traversal of the tree. Each node is visited exactly once due to the memoization using the mp dictionary. When we encounter a node for the first time, we create its copy and recursively process its left, right, and random pointers. If we encounter a node that has already been processed (exists in mp), we simply return the cached copy in O(1) time. Since each node is processed once and each operation per node takes constant time, the overall time complexity is O(n).

Space Complexity: O(n) where n is the number of nodes in the binary tree.

The space complexity consists of two components:

1. HashMap storage (mp): The dictionary stores a mapping from each original node to its corresponding copy, requiring O(n) space for n nodes.
2. Recursion call stack: In the worst case (a skewed tree), the recursion depth can be O(n), requiring O(n) space for the call stack. In the best case (a balanced tree), the recursion depth would be O(log n).

Therefore, the overall space complexity is O(n) dominated by both the HashMap storage and potentially the recursion stack in the worst case.

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

Common Pitfalls

Pitfall 1: Creating the Node Copy After Recursive Calls

The Problem: A common mistake is to create the copied node and store it in the hash map AFTER making the recursive calls:

def dfs(node):
    if node is None:
        return None
  
    if node in node_map:
        return node_map[node]
  
    # WRONG: Recursive calls before creating the copy
    left_copy = dfs(node.left)
    right_copy = dfs(node.right)
    random_copy = dfs(node.random)
  
    # Creating copy after recursion
    copied_node = NodeCopy(node.val)
    copied_node.left = left_copy
    copied_node.right = right_copy
    copied_node.random = random_copy
  
    node_map[node] = copied_node
    return copied_node

Why This Fails: This approach breaks when there are cycles through random pointers. For example:

• If a node's random pointer points to itself
• If there's a cycle: Node A → (random) → Node B → (random) → Node A

The recursion will never terminate because the node isn't in the hash map when we check for it recursively, leading to infinite recursion and stack overflow.

The Solution: Always create the node and cache it in the hash map BEFORE making recursive calls:

def dfs(node):
    if node is None:
        return None
  
    if node in node_map:
        return node_map[node]
  
    # CORRECT: Create and cache first
    copied_node = NodeCopy(node.val)
    node_map[node] = copied_node  # Cache immediately
  
    # Then make recursive calls
    copied_node.left = dfs(node.left)
    copied_node.right = dfs(node.right)
    copied_node.random = dfs(node.random)
  
    return copied_node

Pitfall 2: Using a Local Hash Map Instead of Instance/Closure Variable

The Problem: Creating a new hash map for each recursive call:

def copyRandomBinaryTree(self, root):
    def dfs(node):
        node_map = {}  # WRONG: Local to each call
      
        if node is None:
            return None
          
        if node in node_map:
            return node_map[node]
      
        # ... rest of the logic

Why This Fails: Each recursive call gets its own hash map, so the memoization doesn't work. The same node will be copied multiple times if referenced by multiple random pointers, breaking the pointer relationships in the copied tree.

The Solution: Use a hash map that's shared across all recursive calls, either as:

1. A closure variable (as in the provided solution)
2. An instance variable of the class
3. A parameter passed through the recursion

def copyRandomBinaryTree(self, root):
    node_map = {}  # Shared across all dfs calls
  
    def dfs(node):
        # Uses the closure variable node_map
        if node in node_map:
            return node_map[node]
        # ... rest of the logic

Pitfall 3: Forgetting to Handle the Random Pointer

The Problem: Only copying the tree structure (left and right) but forgetting about the random pointer:

def dfs(node):
    if node is None:
        return None
  
    if node in node_map:
        return node_map[node]
  
    copied_node = NodeCopy(node.val)
    node_map[node] = copied_node
  
    copied_node.left = dfs(node.left)
    copied_node.right = dfs(node.right)
    # WRONG: Forgot to copy random pointer!
  
    return copied_node

Why This Fails: The copied tree will have all random pointers as None or pointing to nodes in the original tree (if you directly assign copied_node.random = node.random), which violates the deep copy requirement.

The Solution: Treat the random pointer the same way as left and right pointers - recursively copy the node it points to:

copied_node.random = dfs(node.random)  # Don't forget this line!