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

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree
Leetcode Link

Problem Description

The problem presents two identical binary trees, original and cloned, meaning that the cloned tree is an exact copy of the original one. Along with these trees, you are given a reference to a node, target, within the original tree. The task is to find and return a reference to the node in the cloned tree that corresponds exactly to the target node in the original tree. It's important to note that you cannot alter either of the trees or the target node in any way; the method must solely locate the corresponding node in the cloned tree.

Intuition

To find a node that corresponds to the target node in the cloned tree, we need to mirror the traversal done in the original tree. Since the cloned tree is an exact copy, every left or right move that leads us to the target node in the original tree will lead us to the corresponding node in the cloned tree.

Therefore, a simple method to solve this problem is to use Depth-First Search (DFS). The dfs function is a recursive method that takes as arguments the current node being examined in original (root1) and the corresponding node in cloned (root2). If root1 is None, we have hit a leaf node, and we return None since there is no corresponding node in cloned. If root1 is the target node, we return root2 since this is the corresponding node in cloned that we are looking for. If we haven't found the target, the search continues recursively in both the left and right children. The or operator is used to return the non-None node โ€“ if the target node is not in the left subtree, the search will continue on the right.

This method ensures that we do a thorough search through both trees simultaneously, comparing nodes from original to the target and from cloned to the identified node in the original tree. When we find the target in original, the same position in cloned will be the node we want to return.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Solution Approach

The reference solution relies on a classic recursive traversal similar to a Depth-First Search (DFS) pattern to navigate through the original and cloned trees. Let's dissect this approach:

  1. DFS Algorithm: At the core of the solution is the recursive DFS algorithm. The algorithm starts from the root node and explores as far as possible along each branch before backtracking. This process naturally fits tree structures and is useful for tree comparison.

  2. Simultaneous Traversal: The solution explores both the original and cloned trees in parallel, passing in corresponding nodes to the recursive dfs function. This ensures that at any recursive call level, root1 from the original tree and root2 from the cloned tree are always nodes at the same position within their respective trees.

  3. Base Cases:

    • If root1 is None, root2 will also point to None in the cloned tree, and the function returns None. This case handles reaching the end of a branch in both trees.
    • If root1 is equal to target, we have found the analogous node in the original tree, so we return root2, which is the corresponding node in the cloned tree.

  4. Recursive Calls:

    • If the target node is not found, the algorithm continues to search recursively in both the left and right children of the current root1 and root2 nodes.
    • The function performs an "or" operation between the returned values of the recursive calls to dfs(root1.left, root2.left) and dfs(root1.right, root2.right). Since Python's or short-circuits, it'll return the first truthy value it encounters. This mechanism is effectively used here to return the non-None node reference once the target node has been found in either the left or right subtree.

  5. Data Structures: The data structure used to carry the nodes during the traversal is the call stack, which is a natural consequence of the recursive approach. There is no need for any additional data structures like lists or dictionaries.

  6. Function Call:

    • The getTargetCopy function initiates the process by calling dfs with the original and cloned root nodes, and it returns whatever node the dfs function finds, which will be the node corresponding to the target node but in the cloned tree.

By taking advantage of the structure and properties of binary trees, as well as the recursive nature of DFS, the solution performs an efficient and straightforward search to find the corresponding node in the cloned tree without additional space complexity outside of the recursive call stack.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Example Walkthrough

Let's consider a very simple example with the following binary trees:

1Original Tree:      Cloned Tree:
2      1                   1
3     / \                 / \
4    2   3               2   3

Assume target is the node with value 2 in the original tree.

We will now walk through the application of the Depth-First Search (DFS) to find the corresponding node in the cloned tree using the steps described in the solution approach:

  1. DFS Algorithm: We initiate a DFS traversal starting from the root node of both the original and the cloned trees.

  2. Simultaneous Traversal: We are at nodes 1 in both the original and the cloned trees. They are corresponding nodes, and neither of them is the target. So we continue the traversal.

  3. Base Cases: The base cases are not met as the root is not None and the root is not equal to the target.

  4. Recursive Calls: We make a recursive call to the left child of the root node:

    • dfs(root1.left, root2.left) is called with root1.left being node 2 in the original tree and root2.left being node 2 in the cloned tree.

  5. Data Structures: The state (current node) is maintained simply within the recursive call stack.

  6. Function Call: Upon the recursive call:

    • We check the base cases again. This time, root1 is equal to target (since both have the value 2), so we return root2, which is the corresponding node in the cloned tree.

By following each step, the algorithm finds the target in the original tree and the corresponding node in the cloned tree without the need for any additional data structures or alterations to the original structures. In this case, the node with value 2 in the cloned tree is returned as the correct answer.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val):
4        self.val = val
5        self.left = None
6        self.right = None
7
8
9class Solution:
10    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
11        """
12        Finds and returns the node in the cloned tree that corresponds to the target node in the original tree.
13
14        Parameters:
15        original : TreeNode
16            The root of the original binary tree.
17        cloned : TreeNode
18            The root of the cloned binary tree, which is an exact copy of the original binary tree.
19        target : TreeNode
20            The target node that exists in the original tree.
21
22        Returns:
23        TreeNode
24            The corresponding node in the cloned tree that matches the target node from the original tree.
25        """
26      
27        # Helper function to perform Depth First Search (DFS) on both trees simultaneously.
28        def dfs(node_original: TreeNode, node_cloned: TreeNode) -> TreeNode:
29            # Base case: if reached the end of the tree, return None.
30            if node_original is None:
31                return None
32          
33            # If the current node in the original tree matches the target, return the corresponding node from cloned tree.
34            if node_original == target:
35                return node_cloned
36          
37            # Recursively search in the left subtree and if not found, then right subtree.
38            found_left = dfs(node_original.left, node_cloned.left)
39            if found_left:
40                return found_left
41            return dfs(node_original.right, node_cloned.right)
42
43        # Call dfs with the root nodes of both the original and cloned trees.
44        return dfs(original, cloned)
45
1// Definition for a binary tree node.
2class TreeNode {
3    int val;
4    TreeNode left;
5    TreeNode right;
6
7    // Constructor for tree node
8    TreeNode(int val) {
9        this.val = val;
10    }
11}
12
13class Solution {
14    private TreeNode targetNode;
15
16    /**
17     * Finds and returns the node in the cloned tree that corresponds to the target node
18     * from the original tree.
19     *
20     * @param original The root node of the original binary tree.
21     * @param cloned The root node of the cloned binary tree, which is an exact copy of the original binary tree.
22     * @param target The target node that needs to be found in the cloned tree.
23     * @return The corresponding node in the cloned tree.
24     */
25    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
26        // Assign the target node to the global variable for reference in DFS.
27        this.targetNode = target;
28        // Start DFS traversal with both trees.
29        return dfs(original, cloned);
30    }
31
32    /**
33     * A helper method to perform DFS on both trees simultaneously.
34     *
35     * @param nodeOriginal The current node in the original tree during the DFS traversal.
36     * @param nodeCloned The current node in the cloned tree during the DFS traversal.
37     * @return The corresponding node in the cloned tree if the target node is found, else null.
38     */
39    private TreeNode dfs(TreeNode nodeOriginal, TreeNode nodeCloned) {
40        // Base case: if the current node in the original tree is null, return null.
41        if (nodeOriginal == null) {
42            return null;
43        }
44        // Check if the current node in the original tree is the target node.
45        if (nodeOriginal == targetNode) {
46            // If the target node is found, return the corresponding node from the cloned tree.
47            return nodeCloned;
48        }
49        // Recursively search in the left subtree.
50        TreeNode result = dfs(nodeOriginal.left, nodeCloned.left);
51        // If the result is not found in the left subtree, search in the right subtree.
52        return result == null ? dfs(nodeOriginal.right, nodeCloned.right) : result;
53    }
54}
55
1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12public:
13    // This method takes the original and cloned trees, along with the target node from the original tree,
14    // and returns the corresponding node from the cloned tree.
15    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
16      
17        // A depth-first search (DFS) lambda function to traverse both trees simultaneously
18        std::function<TreeNode*(TreeNode*, TreeNode*)> dfs = [&](TreeNode* nodeOriginal, TreeNode* nodeCloned) -> TreeNode* {
19            // If the original node is null, return null as the search has reached the end of a branch
20            if (nodeOriginal == nullptr) {
21                return nullptr;
22            }
23          
24            // If the original node is the target node we are searching for, return the corresponding cloned node
25            if (nodeOriginal == target) {
26                return nodeCloned;
27            }
28          
29            // Search in the left subtree
30            TreeNode* leftSubtreeResult = dfs(nodeOriginal->left, nodeCloned->left);
31          
32            // If the left subtree did not contain the target, search in the right subtree;
33            // otherwise, return the result from the left subtree.
34            return leftSubtreeResult == nullptr ? dfs(nodeOriginal->right, nodeCloned->right) : leftSubtreeResult;
35        };
36
37        // Call the DFS function with the original and cloned tree roots to start the search
38        return dfs(original, cloned);
39    }
40};
41
1// Definition for a binary tree node.
2interface TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6}
7
8/**
9 * Finds and returns the node with the same value in the cloned tree as the target node in the original tree.
10 * 
11 * @param original - The root node of the original binary tree
12 * @param cloned - The root node of the cloned binary tree
13 * @param target - The target node that we want to find in the cloned tree
14 * @returns TreeNode | null - The node in the cloned tree that corresponds to the target node in the original tree
15 */
16function getTargetCopy(
17    original: TreeNode | null,
18    cloned: TreeNode | null,
19    target: TreeNode | null
20): TreeNode | null {
21    // Helper function to perform a depth-first search (DFS)
22    const depthFirstSearch = (nodeOriginal: TreeNode | null, nodeCloned: TreeNode | null): TreeNode | null => {
23        // If the current node in the original tree is null, return null since we can't find a corresponding node
24        if (!nodeOriginal) {
25            return null;
26        }
27        // If the current node in the original tree is the target, return the corresponding node in the cloned tree
28        if (nodeOriginal === target) {
29            return nodeCloned;
30        }
31        // Recursively search in the left subtree, and if not found, search in the right subtree.
32        return depthFirstSearch(nodeOriginal.left, nodeCloned.left) || depthFirstSearch(nodeOriginal.right, nodeCloned.right);
33    };
34
35    // Start DFS from the root nodes of both trees
36    return depthFirstSearch(original, cloned);
37}
38
Not Sure What to Study? Take the 2-min Quiz๏ผš

What data structure does Breadth-first search typically uses to store intermediate states?

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(N) where N is the total number of nodes in the tree. This is because the algorithm traverses each node of the binary tree exactly once in the worst case (when the target node is the last one visited or not present at all).

The dfs function is a recursive depth-first search that goes through all nodes of the tree, and for each node, it performs constant-time operations (checking if the node is the target and returning the corresponding node from the cloned tree).

Space Complexity

The space complexity of the provided code is O(H) where H is the height of the binary tree. This is because the maximum amount of space used by the call stack will be due to the depth of the recursive calls, which corresponds to the height of the tree in the worst case.

For a balanced tree, this would be O(log N), where N is the total number of nodes in the tree, because the height of a balanced tree is logarithmic with respect to the number of nodes. However, in the worst case of a skewed tree (i.e., when the tree is a linked list), the space complexity would be O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following problems can be solved with backtracking (select multiple)

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ