LeetCode: 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

The Problem

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.

Example

Input:  tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• The values of the nodes of the tree are unique.
• target node is a node from the original tree and is not null.

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
    TreeNode *ans;
    getTargetCopy(cloned, ans, target->val);
    return ans;
}

void getTargetCopy(TreeNode* root, TreeNode *&ans, int target) {
    if (root == nullptr) return;

    if(root->val == target){
	    ans = root;
    	return;
    } else {
	    getTargetCopy(root->left, ans, target);
    	getTargetCopy(root->right, ans, target);
    }
}

Here's a step-by-step explanation of the code:

1. The main function TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) is the entry point. It takes three parameters:

• original: A pointer to the root of the original binary tree.
• cloned: A pointer to the root of the cloned binary tree.
• target: A pointer to the target node in the original tree that you want to find in the cloned tree.

2. Inside the getTargetCopy function, there's a pointer ans declared to store the result, which is initially uninitialized.

3. The getTargetCopy function is then called with the cloned tree, the ans pointer, and the value of the target node from the original tree (target->val). This initiates the search for the node in the cloned tree that matches the target value.

4. The getTargetCopy function with three parameters is the recursive helper function:

• It first checks if the current node (root) is nullptr, which means it has reached the end of a branch in the cloned tree. In that case, it returns, indicating the search is unsuccessful for this branch.
• If the value of the current node (root->val) matches the target value, it means the target node from the original tree has been found in the cloned tree. In this case, it sets the ans pointer to point to this node and returns. This effectively terminates the search.
• If the current node's value does not match the target, it continues the search recursively by calling getTargetCopy for both the left and right subtrees of the current node.

5. After the recursive search is complete, the main function returns the ans pointer, which now points to the node in the cloned tree that corresponds to the target node in the original tree.