Jobs

Interviews

Discussions

Clone Binary Tree With Random Pointer

Medium

Asked by:

15 views

Topics:

TreesRecursion

A binary tree is given using the helper class Node. Each node has a value and two pointers, left and right, that point to other nodes in the tree. Additionally, each node might have a third pointer, random, which also points to any node in the tree, or null.

Clone the given tree.

Here is an example of the Node class:

class Node {
  int val;
  Node left;
  Node right;
  Node random;
  Node() {}
  Node(int val) { this.val = val; }
  Node(int val, Node left, Node right, Node random) {
      this.val = val;
      this.left = left;
      this.right = right;
      this.random = random;
  }
}

Example 1:

Input: root = [[7,null,null,null],[13,0,null,null],[11,null,4,null],[10,7,null,null],[1,0,null,null],[4,2,null,null]]
Output: [[7,null,null,null],[13,0,null,null],[11,null,4,null],[10,7,null,null],[1,0,null,null],[4,2,null,null]]

Example 2:

Input: root = [[1,null,null,null],[2,0,null,null]]
Output: [[1,null,null,null],[2,0,null,null]]

Constraints:

The number of nodes in the tree is in the range [0, 1000].
-1000 <= Node.val <= 1000
Each node's value is unique.
The input tree is a valid binary tree.

Try coding it in LeetCode

Clone Binary Tree With Random Pointer

Medium

Asked by:

15 views

Topics:

TreesRecursion

Clone the given tree.

Here is an example of the Node class:

class Node {
  int val;
  Node left;
  Node right;
  Node random;
  Node() {}
  Node(int val) { this.val = val; }
  Node(int val, Node left, Node right, Node random) {
      this.val = val;
      this.left = left;
      this.right = right;
      this.random = random;
  }
}

Example 1:

Input: root = [[7,null,null,null],[13,0,null,null],[11,null,4,null],[10,7,null,null],[1,0,null,null],[4,2,null,null]]
Output: [[7,null,null,null],[13,0,null,null],[11,null,4,null],[10,7,null,null],[1,0,null,null],[4,2,null,null]]

Example 2:

Input: root = [[1,null,null,null],[2,0,null,null]]
Output: [[1,null,null,null],[2,0,null,null]]

Constraints:

The number of nodes in the tree is in the range [0, 1000].
-1000 <= Node.val <= 1000
Each node's value is unique.
The input tree is a valid binary tree.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the binary tree be empty, and if so, what should I return?
What are the possible data types and range of values for the node's data?
Is it possible for the random pointer to point to null or to a node outside of the original tree?
Is the original tree a valid binary tree, or could it contain cycles or other structural anomalies that the clone should not replicate?
Should the cloned tree be a deep copy, with completely new node objects, or a shallow copy, and if shallow, what aspects should be a deep copy?

Brute Force Solution

Approach

The challenge is to make a complete copy of a tree, but with an extra twist: each node has a special 'random' pointer that might point to any other node in the original tree. The brute force method makes a new tree and then painstakingly finds the corresponding random node for each node in the copied tree.

Here's how the algorithm would work step-by-step:

First, create a brand new tree structure that perfectly mirrors the original tree's shape and data. Ignore the random pointers for now.
Next, for every node in the new, copied tree, we need to figure out what its random pointer should point to.
For each node in the copied tree, look at the corresponding node in the original tree and see where *its* random pointer points.
Once you find where the original node's random pointer points, you need to find the corresponding node in the *copied* tree.
To find the corresponding node in the copied tree, we'll have to compare every single node in the copied tree with the node that the original's random pointer pointed to.
Once we find the matching node in the copied tree, point the current copied node's random pointer to that found node.
Repeat this process of finding corresponding nodes for *every* node in the copied tree. Once all nodes in the copied tree have their random pointers correctly set, the cloning is complete.

Code Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.random = None

def clone_binary_tree_with_random_pointer_brute_force(root):
    if not root:
        return None

    # Create a deep copy of the tree structure
    copied_root = _clone_tree_structure(root)

    # Assign random pointers in the copied tree
    _assign_random_pointers(root, copied_root)

    return copied_root

def _clone_tree_structure(root):
    if not root:
        return None

    copied_node = Node(root.value)
    copied_node.left = _clone_tree_structure(root.left)
    copied_node.right = _clone_tree_structure(root.right)

    return copied_node

def _assign_random_pointers(original_root, copied_root):
    if not original_root:
        return

    # Need to process the current node first
    _process_current_node(original_root, copied_root)

    _assign_random_pointers(original_root.left, copied_root.left)
    _assign_random_pointers(original_root.right, copied_root.right)

def _process_current_node(original_node, copied_node):
    if original_node.random:
        # Must find corresponding node in copied tree
        copied_node.random = _find_corresponding_node(original_node.random, copied_node)

def _find_corresponding_node(original_random_node, copied_root):
    if not original_random_node:
        return None

    return _brute_force_search(original_random_node, copied_root)

def _brute_force_search(original_random_node, copied_node):
    if not copied_node:
        return None

    if copied_node.value == original_random_node.value:
        # If values match, assume it's the same node
        return copied_node

    # Recursively search left and right subtrees
    left_result = _brute_force_search(original_random_node, copied_node.left)
    if left_result:
        return left_result

    return _brute_force_search(original_random_node, copied_node.right)

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n nodes in the cloned binary tree to determine the random pointer for each clone node. For each of these n nodes in the clone tree, the algorithm searches the entire cloned tree (which has n nodes) to find the corresponding node to which the original tree's random pointer points. This pair checking process within the cloned tree is repeated n times, once for each node needing its random pointer set. Therefore, the total number of operations approximates n * n, which simplifies to O(n²).

Space Complexity

O(1) – The provided solution iterates through the copied tree to find matching nodes, comparing nodes one by one. While this process is time-consuming, it does not require storing additional data structures that scale with the number of nodes in the tree. The algorithm operates in place within the existing copied tree structure after the initial clone. Therefore, the auxiliary space complexity is constant, regardless of the tree size N.

Optimal Solution

Approach

We need to create a perfect copy of a binary tree, but this tree has a special pointer that points to a random node. The trick is to efficiently link the random pointers in the cloned tree to their corresponding nodes in the cloned tree.

Here's how the algorithm would work step-by-step:

First, make a copy of each node in the original tree and store the new node right next to the original node using a map or dictionary.
Now, go through the original tree again. For each node, find its left and right children in the original tree, look up the corresponding cloned nodes in the map, and set the left and right children of the cloned node to these newly found cloned children.
Next, do the same for the random pointers. Look up the node the original node's random pointer is pointing to in the original tree, find its cloned counterpart in the map, and set the cloned node's random pointer to the cloned counterpart.
Finally, return the cloned version of the root node of the original tree. The map holds the relationship between original nodes and cloned nodes, so we can easily and efficiently create the complete clone including the random pointers.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.random = None

def clone_binary_tree_with_random_pointer(root):
    if not root:
        return None

    node_map = {}

    # Create clone nodes and store them in the map
    def create_clones(node):
        if not node:
            return
        node_map[node] = TreeNode(node.value)
        create_clones(node.left)
        create_clones(node.right)

    create_clones(root)

    # Set left and right pointers of the cloned nodes
    def assign_left_right(node):
        if not node:
            return

        cloned_node = node_map[node]
        if node.left:
            cloned_node.left = node_map[node.left]
        if node.right:
            cloned_node.right = node_map[node.right]

        assign_left_right(node.left)
        assign_left_right(node.right)

    assign_left_right(root)

    # Assign random pointers of the cloned nodes
    def assign_random_pointers(node):
        if not node:
            return

        cloned_node = node_map[node]
        
        # Must check if random pointer is not null
        if node.random:
            cloned_node.random = node_map[node.random]

        assign_random_pointers(node.left)
        assign_random_pointers(node.right)

    assign_random_pointers(root)

    # Return the cloned root
    return node_map[root]

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each of the n nodes in the binary tree a fixed number of times. First, it iterates through the tree to create clones and store them in a map. Second, it iterates again to link the left and right children. Third, it iterates one last time to link the random pointers. Each lookup and insertion in the map takes constant time. Therefore, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm uses a map (or dictionary) to store the correspondence between original nodes and cloned nodes. In the worst-case scenario, where the binary tree is highly unbalanced, the map will contain entries for all N nodes of the original tree. Therefore, the space required by the map scales linearly with the number of nodes in the original tree, contributing O(N) space complexity. No other significant auxiliary data structures are employed beyond this map.

Edge Cases

Case	How to Handle
Null root node	Return null immediately if the root is null, indicating an empty tree.
Single node tree	Create a new node with the same value and set its random pointer to null, then return the new node.
Tree with all nodes having the same value	The hash map will correctly map all original nodes to new nodes with the same value, ensuring a correct clone.
Tree with skewed structure (e.g., only left or right children)	Recursion handles this case without stack overflow, as each node is still visited and cloned.
Random pointers forming cycles or pointing to nodes outside the subtree	The hash map ensures that the clone of a node already exists and is reused if the random pointer points to it.
Large tree (potential for stack overflow with recursion)	Use iterative DFS with a stack to avoid stack overflow for large trees.
Original tree modified during cloning	The hashmap stores mapping of old node to new node, thus not being affacted by modifications in original tree.
Memory constraints for extremely large trees	Consider using an external memory store or a more memory-efficient data structure if the cloned tree becomes too large to fit in memory.

Null root node

How to Handle:

Return null immediately if the root is null, indicating an empty tree.

Single node tree

How to Handle:

Create a new node with the same value and set its random pointer to null, then return the new node.

Tree with all nodes having the same value

How to Handle:

The hash map will correctly map all original nodes to new nodes with the same value, ensuring a correct clone.

Tree with skewed structure (e.g., only left or right children)

How to Handle:

Recursion handles this case without stack overflow, as each node is still visited and cloned.

Random pointers forming cycles or pointing to nodes outside the subtree

How to Handle:

The hash map ensures that the clone of a node already exists and is reused if the random pointer points to it.

Large tree (potential for stack overflow with recursion)

How to Handle:

Use iterative DFS with a stack to avoid stack overflow for large trees.

Original tree modified during cloning

How to Handle:

The hashmap stores mapping of old node to new node, thus not being affacted by modifications in original tree.

Memory constraints for extremely large trees

How to Handle:

Consider using an external memory store or a more memory-efficient data structure if the cloned tree becomes too large to fit in memory.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the binary tree be empty, and if so, what should I return?
What are the possible data types and range of values for the node's data?
Is it possible for the random pointer to point to null or to a node outside of the original tree?
Is the original tree a valid binary tree, or could it contain cycles or other structural anomalies that the clone should not replicate?
Should the cloned tree be a deep copy, with completely new node objects, or a shallow copy, and if shallow, what aspects should be a deep copy?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, create a brand new tree structure that perfectly mirrors the original tree's shape and data. Ignore the random pointers for now.
Next, for every node in the new, copied tree, we need to figure out what its random pointer should point to.
For each node in the copied tree, look at the corresponding node in the original tree and see where *its* random pointer points.
Once you find where the original node's random pointer points, you need to find the corresponding node in the *copied* tree.
To find the corresponding node in the copied tree, we'll have to compare every single node in the copied tree with the node that the original's random pointer pointed to.
Once we find the matching node in the copied tree, point the current copied node's random pointer to that found node.
Repeat this process of finding corresponding nodes for *every* node in the copied tree. Once all nodes in the copied tree have their random pointers correctly set, the cloning is complete.

Code Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.random = None

def clone_binary_tree_with_random_pointer_brute_force(root):
    if not root:
        return None

    # Create a deep copy of the tree structure
    copied_root = _clone_tree_structure(root)

    # Assign random pointers in the copied tree
    _assign_random_pointers(root, copied_root)

    return copied_root

def _clone_tree_structure(root):
    if not root:
        return None

    copied_node = Node(root.value)
    copied_node.left = _clone_tree_structure(root.left)
    copied_node.right = _clone_tree_structure(root.right)

    return copied_node

def _assign_random_pointers(original_root, copied_root):
    if not original_root:
        return

    # Need to process the current node first
    _process_current_node(original_root, copied_root)

    _assign_random_pointers(original_root.left, copied_root.left)
    _assign_random_pointers(original_root.right, copied_root.right)

def _process_current_node(original_node, copied_node):
    if original_node.random:
        # Must find corresponding node in copied tree
        copied_node.random = _find_corresponding_node(original_node.random, copied_node)

def _find_corresponding_node(original_random_node, copied_root):
    if not original_random_node:
        return None

    return _brute_force_search(original_random_node, copied_root)

def _brute_force_search(original_random_node, copied_node):
    if not copied_node:
        return None

    if copied_node.value == original_random_node.value:
        # If values match, assume it's the same node
        return copied_node

    # Recursively search left and right subtrees
    left_result = _brute_force_search(original_random_node, copied_node.left)
    if left_result:
        return left_result

    return _brute_force_search(original_random_node, copied_node.right)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, make a copy of each node in the original tree and store the new node right next to the original node using a map or dictionary.
Now, go through the original tree again. For each node, find its left and right children in the original tree, look up the corresponding cloned nodes in the map, and set the left and right children of the cloned node to these newly found cloned children.
Next, do the same for the random pointers. Look up the node the original node's random pointer is pointing to in the original tree, find its cloned counterpart in the map, and set the cloned node's random pointer to the cloned counterpart.
Finally, return the cloned version of the root node of the original tree. The map holds the relationship between original nodes and cloned nodes, so we can easily and efficiently create the complete clone including the random pointers.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.random = None

def clone_binary_tree_with_random_pointer(root):
    if not root:
        return None

    node_map = {}

    # Create clone nodes and store them in the map
    def create_clones(node):
        if not node:
            return
        node_map[node] = TreeNode(node.value)
        create_clones(node.left)
        create_clones(node.right)

    create_clones(root)

    # Set left and right pointers of the cloned nodes
    def assign_left_right(node):
        if not node:
            return

        cloned_node = node_map[node]
        if node.left:
            cloned_node.left = node_map[node.left]
        if node.right:
            cloned_node.right = node_map[node.right]

        assign_left_right(node.left)
        assign_left_right(node.right)

    assign_left_right(root)

    # Assign random pointers of the cloned nodes
    def assign_random_pointers(node):
        if not node:
            return

        cloned_node = node_map[node]
        
        # Must check if random pointer is not null
        if node.random:
            cloned_node.random = node_map[node.random]

        assign_random_pointers(node.left)
        assign_random_pointers(node.right)

    assign_random_pointers(root)

    # Return the cloned root
    return node_map[root]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null root node	Return null immediately if the root is null, indicating an empty tree.
Single node tree	Create a new node with the same value and set its random pointer to null, then return the new node.
Tree with all nodes having the same value	The hash map will correctly map all original nodes to new nodes with the same value, ensuring a correct clone.
Tree with skewed structure (e.g., only left or right children)	Recursion handles this case without stack overflow, as each node is still visited and cloned.
Random pointers forming cycles or pointing to nodes outside the subtree	The hash map ensures that the clone of a node already exists and is reused if the random pointer points to it.
Large tree (potential for stack overflow with recursion)	Use iterative DFS with a stack to avoid stack overflow for large trees.
Original tree modified during cloning	The hashmap stores mapping of old node to new node, thus not being affacted by modifications in original tree.
Memory constraints for extremely large trees	Consider using an external memory store or a more memory-efficient data structure if the cloned tree becomes too large to fit in memory.

Null root node

How to Handle:

Return null immediately if the root is null, indicating an empty tree.

Single node tree

How to Handle:

Create a new node with the same value and set its random pointer to null, then return the new node.

Tree with all nodes having the same value

How to Handle:

The hash map will correctly map all original nodes to new nodes with the same value, ensuring a correct clone.

Tree with skewed structure (e.g., only left or right children)

How to Handle:

Recursion handles this case without stack overflow, as each node is still visited and cloned.

Random pointers forming cycles or pointing to nodes outside the subtree

How to Handle:

The hash map ensures that the clone of a node already exists and is reused if the random pointer points to it.

Large tree (potential for stack overflow with recursion)

How to Handle:

Use iterative DFS with a stack to avoid stack overflow for large trees.

Original tree modified during cloning

How to Handle:

The hashmap stores mapping of old node to new node, thus not being affacted by modifications in original tree.

Memory constraints for extremely large trees

How to Handle:

Consider using an external memory store or a more memory-efficient data structure if the cloned tree becomes too large to fit in memory.