C++ | Find a Corresponding Node of a Binary Tree in a Clone of That Tree | General tree traversal
175

Problem Statement : https://leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/579/week-1-january-1st-january-7th/3590/

We can do any tree traversal and check the target node value with the current node value and if same we can return it.

Here we used DFS traversal, if you are not aware of it please go through the below link.
https://en.wikipedia.org/wiki/Depth-first_search#:~:text=Depth%2Dfirst%20search%20(DFS),along%20each%20branch%20before%20backtracking.

Note: Since they didn't mentioned about duplicates no need of original tree.
But the best pratice would be comparing with original tree also.

The follwing are two approaches with and wihtout using original tree -

Approach-1: Without using original tree
  1. Here we have applied dfs + preorder over the tree (can also use inorder or postorder).
  2. If root node is empyt or leaf node return nullptr stating empty.
  3. If required target value is same as root node value return root (here root means node in a cloned tree).
  4. Check for left and right subtrees and if any of them find the target return it.
class Solution {
public:
    
    TreeNode* dfs(TreeNode* root, TreeNode* target) {
        if(!root) return nullptr;
        if(root -> val == target -> val) return root;
        TreeNode* left =  dfs(root -> left, target);
        TreeNode* right =  dfs(root -> right, target);
        if(left) return left;
        return right;
    }
    
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        return dfs(cloned, target -> val);
    }
};

Approach-2: Comparing with original tree
  1. As discussed earlier, incase of duplicates the above mentioned algorithm would fail by returning some other node with same value.
  2. So, by comparing target node directly with the orginal tree nodes we can get correct result in case of duplicate values.
  3. When we hit exact target node in original tree we return it's correspondent node in cloned tree.
class Solution {
public:
    TreeNode* dfs(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        if(!original) return nullptr;
        if(original == target) return cloned;
        TreeNode* left =  dfs(original -> left, cloned -> left, target);
        TreeNode* right =  dfs(original -> right, cloned -> right ,target);
        if(left) return left;
        return right;
    }
    
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        return dfs(original, cloned, target);
    }
};

Upvote if you like.
Thank you.

Comments (1)