Clone Binary Tree With Random Pointer

Clone Binary Tree With Random Pointer

What is this problem about?

You are given a binary tree where each node has a left child, a right child, and a random pointer that points to any node in the tree or null. You need to create a "deep copy" of this tree. A deep copy means all nodes in the new tree must be new instances, and all pointers (including the random ones) must point to the corresponding nodes in the new tree.

Why is this asked in interviews?

Meta and Amazon use this "Medium" problem to test your ability to handle complex object references and graph traversal. It’s a variation of the "Clone Graph" problem. The main challenge is that when you are cloning a node, its random pointer might point to a node you haven't created yet. It evaluations your skill in using a Hash Table to map original nodes to their copies.

Algorithmic pattern used

The pattern is Graph Traversal (DFS or BFS) with a Hash Table.

1. Perform a first pass (or use recursion) to traverse the tree.
2. For each original node, create a new copy and store the mapping map[old_node] = new_node.
3. Perform a second pass (or complete the recursion) to set the left, right, and random pointers of the new nodes using the map: new_node.random = map[old_node.random].

Example explanation

1. Node A points to B (left) and C (random).
2. Create copy A'. Store map[A] = A'.
3. Create copy B'. Store map[B] = B'.
4. Create copy C'. Store map[C] = C'.
5. Now, set A'.left = map[B] = B'.
6. Set A'.random = map[C] = C'. This ensures the copy structure exactly mirrors the original.

Common mistakes candidates make

The most common mistake is a "shallow copy," where the new tree still points to nodes in the original tree. Another is not handling null pointers correctly. Some might also try to solve it without a map, which is much more difficult and usually requires multiple passes or structural modifications to the original tree.

Interview preparation tip

Any "cloning" problem involving random or arbitrary pointers requires a way to "remember" which copy corresponds to which original. A Hash Table (Map) is the most straightforward and efficient way to achieve this.