Clone Binary Tree With Random Pointer

medium tree dfs bfs hash map

Problem

Given a binary tree where each node also has a random pointer, return a deep copy preserving left, right, and random links.

Inputtree [1,null,4,7,3,null,null,#] with random links

Outputdeep clone with identical structure

Use a NodeOriginal → NodeCloned hash map.

tree (level-order)

random pairs JSON {from:to}

def copy_random_binary_tree(root):
    if not root: return None
    seen = {}
    def clone(n):
        if not n: return None
        if n in seen: return seen[n]
        nc = Node(n.val); seen[n] = nc
        nc.left = clone(n.left); nc.right = clone(n.right); nc.random = clone(n.random)
        return nc
    return clone(root)

function copyRandomBinaryTree(root) {
  const seen = new Map();
  function clone(n) {
    if (!n) return null;
    if (seen.has(n)) return seen.get(n);
    const nc = { val: n.val, left: null, right: null, random: null };
    seen.set(n, nc);
    nc.left = clone(n.left); nc.right = clone(n.right); nc.random = clone(n.random);
    return nc;
  }
  return clone(root);
}

class Solution {
    Map seen = new HashMap<>();
    public NodeCopy copyRandomBinaryTree(Node root) {
        if (root == null) return null;
        if (seen.containsKey(root)) return seen.get(root);
        NodeCopy n = new NodeCopy(root.val);
        seen.put(root, n);
        n.left = copyRandomBinaryTree(root.left);
        n.right = copyRandomBinaryTree(root.right);
        n.random = copyRandomBinaryTree(root.random);
        return n;
    }
}

class Solution {
    unordered_map seen;
public:
    NodeCopy* copyRandomBinaryTree(Node* root) {
        if (!root) return nullptr;
        if (seen.count(root)) return seen[root];
        NodeCopy* n = new NodeCopy(root->val);
        seen[root] = n;
        n->left = copyRandomBinaryTree(root->left);
        n->right = copyRandomBinaryTree(root->right);
        n->random = copyRandomBinaryTree(root->random);
        return n;
    }
};

Explanation

Each node has a random pointer that can jump anywhere in the tree, so a plain recursive copy could try to clone the same node many times or loop forever. The fix is a hash map that remembers, for each original node, its clone.

The recursive clone(n) first checks the map seen. If n is already there, it returns the existing copy immediately — this prevents duplicate clones and breaks any cycles caused by random links.

Otherwise it creates a fresh node nc with the same value and, crucially, stores it in the map before recursing. Only then does it clone the left, right, and random children. Because the map entry exists first, a random pointer that points back to n will find the copy instead of recursing again.

Example: if node A's random points to B and B's random points back to A, cloning A registers A→A', then clones B (registering B→B'), and when B' needs A' the map already has it — no infinite loop.

Every node is created exactly once and the map gives constant-time lookups, so the clone runs in O(n) time and O(n) space.

Time: O(n) Space: O(n)