Is Clone Binary Tree With Random Pointer easy or hard?

Clone Binary Tree With Random Pointer is generally rated Medium difficulty. The tree traversal itself is straightforward, but correctly handling random pointers requires recognizing the structure as a graph and using a hash map to avoid duplicating nodes.

Clone Binary Tree With Random Pointer Python/Java solution

Both Python and Java implementations typically use a HashMap or dictionary with DFS recursion. The function creates a clone node, stores it in the map, and recursively assigns left, right, and random pointers using the stored mappings. The algorithm stays O(n) time and O(n) space in either language.

How to solve Clone Binary Tree With Random Pointer in O(n)?

Traverse the tree using DFS or BFS while maintaining a hash map from original nodes to cloned nodes. When visiting a node, create its clone if it does not already exist in the map. Then connect its left, right, and random pointers using references from the same map. Each node is processed once, giving O(n) time complexity.

What is the best approach for Clone Binary Tree With Random Pointer?

The most common approach uses a hash map with DFS traversal. Each original node is mapped to its cloned node so that left, right, and random pointers can be assigned correctly. This prevents duplicate node creation and ensures every reference points to the correct clone. The solution runs in O(n) time and O(n) space.

Is Clone Binary Tree With Random Pointer asked at Google/Amazon/Meta?

Pointer cloning problems with random references appear in interviews at companies like Amazon, Google, and Meta because they test graph thinking and pointer manipulation. Variants such as Copy List with Random Pointer and cloning graph structures are especially common.

What data structure is used in Clone Binary Tree With Random Pointer?

A hash table (or hash map) is the key data structure. It stores the mapping between each original node and its cloned node so multiple pointers referencing the same node resolve correctly. Tree traversal is performed using DFS recursion or a BFS queue.

What is the time complexity of Clone Binary Tree With Random Pointer?

The optimal solution runs in O(n) time because every node in the tree is visited once and each pointer assignment is a constant-time hash lookup. Space complexity is O(n) due to the hash map that stores mappings between original nodes and cloned nodes, plus recursion or queue storage.

Description Hints 2 Solution Video 7:49

1485. Clone Binary Tree With Random Pointer

Medium81.2% acceptance2 companiesPremium elsewhere, free here

A binary tree is given such that each node contains an additional random pointer which could point to any node in the tree or null.

Return a deep copy of the tree.

The tree is represented in the same input/output way as normal binary trees where each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (in the input) where the random pointer points to, or null if it does not point to any node.

You will be given the tree in class Node and you should return the cloned tree in class NodeCopy. NodeCopy class is just a clone of Node class with the same attributes and constructors.

Example 1:

Input: root = [[1,null],null,[4,3],[7,0]]
Output: [[1,null],null,[4,3],[7,0]]
Explanation: The original binary tree is [1,null,4,7].
The random pointer of node one is null, so it is represented as [1, null].
The random pointer of node 4 is node 7, so it is represented as [4, 3] where 3 is the index of node 7 in the array representing the tree.
The random pointer of node 7 is node 1, so it is represented as [7, 0] where 0 is the index of node 1 in the array representing the tree.

Example 2:

Input: root = [[1,4],null,[1,0],null,[1,5],[1,5]]
Output: [[1,4],null,[1,0],null,[1,5],[1,5]]
Explanation: The random pointer of a node can be the node itself.

Example 3:

Input: root = [[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0]]
Output: [[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0]]

Constraints:

The number of nodes in the tree is in the range [0, 1000].
1 <= Node.val <= 10⁶

Asked at 2 companies

Amazon Meta

Topics

Hints open one at a time

Hint 1

Traverse the tree, keep a hashtable with you and create a nodecopy for each node in the tree.

Hint 2

Start traversing the original tree again and connect the left, right and random pointers in the cloned tree the same way as the original tree with the help of the hashtable.

7:49

Still stuck?Read the written solution, or watch a walkthrough.

Open solution