Find a Corresponding Node of a Binary Tree in a Clone of That Tree- Leetcode (Medium Level)

January Leetcode Challenge

Question:

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Solve the problem if repeated values on the tree are allowed.

Intuition:

1. Transverse through the Cloned binary tree and if the value of any node in the Cloned tree is equal to target node’s value, return that node of Cloned tree. This solution would be correct if all the node values are unique.
2. Map every node of the Cloned tree with its corresponding Original tree node. Where key is the Original tree’s node and the value is the Cloned tree’s node. Finally return the value from the map at the target node given in the problem. This is the correct solution for this problem and I will be providing my code for this approach below in C++;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    unordered_map<TreeNode*, TreeNode*> ma;
    //inorder traversal of binary tree;
    void fillMap(TreeNode* original, TreeNode* cloned){
        if(!original)return;
        fillMap(original->left,cloned->left);
        ma[original]=cloned;
        fillMap(original->right,cloned->right);
    }
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        fillMap(original,cloned);
        return ma[target];
    }
};

Input is taken by the Leetcode compiler and struct TreeNode{}; was also by default created by Leetcode compiler; we just have to implement the function “getTargetCopy()”;

I used unordered_map instead of normal map because unordered_map is faster than map and I didn’t wanted my keys to be sorted.

map keeps keys values in sorted order but unordered_map doesn’t.

For this I have created a private unordered_map and a fillMap() function. I performed inorder traversal recursively on both trees to fill my map with correct values and then finally returned my target value from map in getTargetCopy() function;

Time and space complexity of the above solution are:

Time complexity is O(n) and Space complexity in O(n), where n is the number of nodes in the tree.