Clone Binary Tree With Random Pointer - Solution & Explanation

Problem Overview: You are given a binary tree where every node contains left, right, and an additional random pointer that can point to any node in the tree (or null). The goal is to create a deep copy of the entire structure so that the new tree has identical connections but uses completely new nodes.

Approach 1: Depth-First Search with Hash Map (O(n) time, O(n) space)

The cleanest strategy is to traverse the tree using DFS and maintain a HashMap that maps each original node to its cloned counterpart. When you first encounter a node, create its clone and store the mapping. Then recursively clone the left, right, and random references using the same map so repeated nodes are reused instead of duplicated.

The key insight: the random pointer can point anywhere in the tree, even to nodes that appear later in traversal. The hash map guarantees that every node is created exactly once and reused whenever another pointer references it. Each node is visited a single time, giving O(n) time complexity and O(n) extra space for the map and recursion stack. This pattern appears frequently in pointer-copy problems and combines ideas from Hash Table lookups and Depth-First Search.

Approach 2: Breadth-First Search with Hash Map (O(n) time, O(n) space)

An iterative alternative uses BFS with a queue. Start by cloning the root and storing the mapping from original node to cloned node. While processing nodes from the queue, create clones for their left, right, and random neighbors if they do not exist yet in the map. Each pointer assignment simply references the already-created clone from the hash table.

This approach processes the structure level by level, which some engineers prefer when recursion depth might become large. Every node still enters the queue once, and each pointer assignment is a constant-time hash lookup. Time complexity remains O(n) and the auxiliary space is O(n) due to the map and queue. The traversal mechanics mirror typical Breadth-First Search used on a Binary Tree.

Recommended for interviews: DFS with a hash map is the most common solution interviewers expect. It demonstrates that you recognize the graph-like structure created by the random pointer and avoid duplicate node creation. Mentioning the BFS variant shows you understand that the core idea is the mapping between original and cloned nodes, while traversal order is flexible.