Problem Description

Given the root of a binary tree where each node contains an additional pointer called random that can point to any node in the tree or be null, your task is to clone the entire tree. The cloned tree should have the same structure, values, and random pointer connections as the original, but must be composed entirely of newly created nodes (i.e., do not reuse any existing nodes from the input tree).

You are guaranteed that there is only one valid solution, and you must not modify the original tree or reuse its nodes. The function signature typically looks like:

class Node {
    int val;
    Node left;
    Node right;
    Node random;
}
Node copyRandomBinaryTree(Node root)
    

Thought Process

At first glance, cloning a binary tree is straightforward: traverse the tree and copy each node and its left/right pointers. However, the random pointer introduces complexity, as it can point to any node in the tree (not just children or parents), or be null.

A brute-force approach might attempt to clone the tree structure first, then for each node, search for the corresponding random target in the cloned tree by value. But this is inefficient, especially if values are duplicated or the tree is large.

To optimize, we need a way to quickly find the cloned counterpart of any original node. This suggests mapping each original node to its clone as we traverse the tree—much like how we handle the "Copy List with Random Pointer" problem for linked lists.

Solution Approach

The optimal solution uses a hash map (dictionary) to map each original node to its corresponding newly created clone node. Here’s the step-by-step approach:

1. Create a mapping: Use a hash map to record the relationship between each original node and its cloned node. This allows us to find the clone of any node in O(1) time.
2. Clone nodes recursively or iteratively: Traverse the tree (DFS or BFS). For each node:
   • If the node hasn't been cloned yet, create a new node with the same value and store it in the map.
   • Recursively clone the left and right children, setting the pointers in the clone.
   • Recursively clone the random pointer, using the map to avoid duplicating nodes and to handle cycles.
3. Return the cloned root: After the traversal, the map will contain all the original-to-clone relationships, and the new tree will be fully constructed with correct random pointers.

This approach ensures that each node is cloned exactly once, and all pointers (including random) are set correctly in a single pass.

Example Walkthrough

Example:
Consider a tree:

        1
       / \
      2   3
    

• Node 1's random points to Node 3
• Node 2's random points to Node 1
• Node 3's random is null

1. We start cloning at root (Node 1). Create its clone and add to the map: map[Node1] = Node1'.
2. Move to Node 1's left child (Node 2). Clone it: map[Node2] = Node2'.
3. Node 2's random points to Node 1. The map already contains Node1', so set Node2'.random = Node1'.
4. Node 1's right child (Node 3). Clone it: map[Node3] = Node3'.
5. Node 3's random is null, so Node3'.random = null.
6. Node 1's random points to Node 3, so Node1'.random = Node3'.
7. The cloned tree now mirrors the structure and random pointers of the original.

Code Implementation

# Definition for a Node.
class Node:
    def __init__(self, val=0, left=None, right=None, random=None):
        self.val = val
        self.left = left
        self.right = right
        self.random = random

class Solution:
    def copyRandomBinaryTree(self, root: 'Node') -> 'Node':
        old_to_new = {}

        def clone(node):
            if not node:
                return None
            if node in old_to_new:
                return old_to_new[node]
            copy = Node(node.val)
            old_to_new[node] = copy
            copy.left = clone(node.left)
            copy.right = clone(node.right)
            copy.random = clone(node.random)
            return copy

        return clone(root)
      

// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* random;
    Node(int _val) {
        val = _val;
        left = nullptr;
        right = nullptr;
        random = nullptr;
    }
};

class Solution {
public:
    unordered_map<Node*, Node*> oldToNew;

    Node* clone(Node* node) {
        if (!node) return nullptr;
        if (oldToNew.count(node)) return oldToNew[node];
        Node* copy = new Node(node->val);
        oldToNew[node] = copy;
        copy->left = clone(node->left);
        copy->right = clone(node->right);
        copy->random = clone(node->random);
        return copy;
    }

    Node* copyRandomBinaryTree(Node* root) {
        return clone(root);
    }
};
      

// Definition for a Node.
class Node {
    int val;
    Node left;
    Node right;
    Node random;
    Node(int val) { this.val = val; }
}

class Solution {
    Map<Node, Node> oldToNew = new HashMap<>();

    private Node clone(Node node) {
        if (node == null) return null;
        if (oldToNew.containsKey(node)) return oldToNew.get(node);
        Node copy = new Node(node.val);
        oldToNew.put(node, copy);
        copy.left = clone(node.left);
        copy.right = clone(node.right);
        copy.random = clone(node.random);
        return copy;
    }

    public Node copyRandomBinaryTree(Node root) {
        return clone(root);
    }
}
      

/**
 * // Definition for a Node.
 * function Node(val, left, right, random) {
 *     this.val = val;
 *     this.left = left;
 *     this.right = right;
 *     this.random = random;
 * }
 */

var copyRandomBinaryTree = function(root) {
    const oldToNew = new Map();

    function clone(node) {
        if (node === null) return null;
        if (oldToNew.has(node)) return oldToNew.get(node);
        const copy = new Node(node.val, null, null, null);
        oldToNew.set(node, copy);
        copy.left = clone(node.left);
        copy.right = clone(node.right);
        copy.random = clone(node.random);
        return copy;
    }

    return clone(root);
};
      

Time and Space Complexity

Brute-force approach:

• Time: O(N^2) — For each node, finding the random target in the clone can take O(N) time.
• Space: O(N) — For the cloned nodes.

• Time: O(N) — Each node is visited once, and all operations (map lookups, assignments) are O(1).
• Space: O(N) — For the hash map and the new tree nodes.

Here, N is the number of nodes in the tree. The hash map enables constant-time access to any node's clone, making the algorithm efficient.

Summary

Cloning a binary tree with random pointers is best solved by mapping each original node to its clone during traversal. This ensures that all pointers—including random pointers, which may point anywhere—are set correctly and efficiently. By leveraging a hash map, we achieve O(N) time and space complexity, and the approach elegantly handles cycles and arbitrary random connections.