We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Clone Binary Tree With Random Pointer

Number: 1624

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given a binary tree where every node has an additional pointer called "random" that can point to any node in the tree (or null), create a deep copy of the tree. Each node in the input tree is represented as a pair [val, random_index] (along with standard left/right pointer structure), and the output should mirror the same structure. The challenge lies in copying both the tree connections (left/right) and the arbitrary random pointer links correctly.

Key Insights

  • Use a hash table (or dictionary) to map each original node to its corresponding cloned node.
  • Traverse the tree (using DFS or BFS) to clone the nodes without worrying initially about their random pointers.
  • In a second traversal, update the left, right, and random pointers in the cloned nodes by referring to the mapping.
  • Handle null cases carefully to avoid dereferencing null pointers.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, as we traverse all nodes. Space Complexity: O(n), needed to store the mapping/dictionary and the cloned nodes.

Solution

The approach used is a two-pass traversal:

  1. First, perform a traversal (DFS or BFS) to create a copy of every node. During this phase, use a hash table to map each original node to its new copy. This helps in later connecting the pointers correctly.
  2. Second, traverse the tree again and set the left, right, and random pointers for each cloned node. For each pointer, refer to the hash table to find the corresponding cloned node. Key data structures:
  • A dictionary (or hash map) to store the mapping between original nodes and their clones.
  • Recursive or iterative traversal (DFS/BFS) to process each node.

The trick is to ensure that whenever you are about to set a pointer (left, right, or random), you have already created the corresponding copy or can create it on the fly using the mapping.

Code Solutions

# Definition for the original Node and the cloned NodeCopy.
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 NodeCopy:
    def __init__(self, val=0, left=None, right=None, random=None):
        self.val = val
        self.left = left
        self.right = right
        self.random = random

def cloneTree(root):
    # Dictionary to map original nodes to their cloned NodeCopy instances
    old_to_new = {}

    # DFS traversal to clone the nodes (first pass)
    def cloneNodes(node):
        if node is None:
            return None
        # If node is already cloned, return it
        if node in old_to_new:
            return old_to_new[node]
        # Create a new cloned node without pointers set yet
        cloned_node = NodeCopy(node.val)
        old_to_new[node] = cloned_node
        # Recursively clone the left and right subtrees
        cloned_node.left = cloneNodes(node.left)
        cloned_node.right = cloneNodes(node.right)
        return cloned_node

    # Start cloning from the root
    cloned_root = cloneNodes(root)

    # Second pass: set up the random pointer for each cloned node
    def setRandomPointers(node):
        if node is None:
            return
        # Set the random pointer for the cloned node using the mapping.
        if node.random:
            old_to_new[node].random = old_to_new[node.random]
        # Recurse for left and right children.
        setRandomPointers(node.left)
        setRandomPointers(node.right)

    setRandomPointers(root)
    return cloned_root

# Example usage:
# root = Node(...)  # Create the original tree here
# cloned_root = cloneTree(root)
← Back to All Questions