🌱 Keegan's Digital Garden

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

2 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- if the node values are unique, then we don't exactly need to care about the contents of the original tree
- we can do a DFS traversal with a helper function, passing through the root of the cloned tree, and the value of the target node, once we find the target node, return it

🤔What Did I Struggle With?

💡 Explanation of Solution

same as initial thoughts ^

if the node values are **NOT** unique:

1. Base Case:
	- if the current node in the original tree is nullptr, return nullptr

2. Target Found:
	- if the current node in the original tree matches the target, return the corresponding node from the cloned tree

3. Recursive Calls:
	- recursively search the left subtree, if the target is found in the left subtree, return the result
	- if not found in the left subtree, search the right subtree

4. DFS Logic in getTargetCopy:
	- the getTargetCopy function calls the dfs function starting from the roots of both trees

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(h) where h is the height of the tree, which is the call stack space associated with the recursion

💻 Implementation of Solution

class Solution {
public:
 
    TreeNode* dfs(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        // Base case: reached a null node
        if (original == nullptr) return nullptr;
        
        // Found the target in the original tree
        if (original == target) return cloned;
 
        // Search in the left subtree
        TreeNode* leftResult = dfs(original->left, cloned->left, target);
        if (leftResult != nullptr) return leftResult;
 
        // Search in the right subtree
        return dfs(original->right, cloned->right, target);
    }
 
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        return dfs(original, cloned, target);
    }
};

Graph View