Clone Binary Tree With Random Pointer Solution

Language Options

Problem Description

So, you think you can just clone a binary tree, huh? Well, hold your horses! This isn’t your average tree cloning exercise. Imagine you have a tree that not only has left and right children but also a random pointer that can point to any node in the tree. It’s like trying to clone your friend’s chaotic family tree where everyone is related in the most confusing ways possible.

In this problem, you are tasked with creating a deep copy of a binary tree where each node has a random pointer. If you think this is as easy as copying a recipe from your neighbor, think again! You need to ensure that the random pointers in the cloned tree point to the same nodes as in the original tree.

Code Solution


class Solution {
 public:
  NodeCopy* copyRandomBinaryTree(Node* root) {
    if (root == nullptr)
      return nullptr;
    if (const auto it = map.find(root); it != map.cend())
      return it->second;

    NodeCopy* newNode = new NodeCopy(root->val);
    map[root] = newNode;

    newNode->left = copyRandomBinaryTree(root->left);
    newNode->right = copyRandomBinaryTree(root->right);
    newNode->random = copyRandomBinaryTree(root->random);
    return newNode;
  }

 private:
  unordered_map map;
};

Approach

The approach taken in this solution is quite straightforward yet clever. It uses a recursive function to traverse the original binary tree. For each node, it checks if it has already been cloned (using a hash map). If it has, it simply returns the cloned node. If not, it creates a new node, stores it in the map, and recursively clones the left, right, and random pointers. This way, you ensure that every node is cloned exactly once, and the random pointers are correctly assigned.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N), where N is the number of nodes in the tree. Each node is visited once.
Space Complexity	O(N) for the hash map that stores the mapping of original nodes to their clones.

Real-World Example

Imagine you’re trying to clone your social media profile, but instead of just copying your posts and pictures, you also want to keep track of all your friends and their connections. Some of your friends might be connected to each other in ways that are not just linear (like a family tree), but also random (like that one friend who knows everyone). This problem is akin to that scenario, where you need to ensure that all connections (or pointers) are preserved in the cloned version.