Find a Corresponding Node of a Binary Tree in a Clone of That Tree — LeetCode 1379 Python Solution

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Problem: #1379
Pattern: Tree Traversal
Reading time: 4 min
Source: leetcode.com

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.

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.

Python solution

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def getTargetCopy(
        self, original: TreeNode, cloned: TreeNode, target: TreeNode
    ) -> TreeNode:
        def dfs(root1: TreeNode, root2: TreeNode) -> TreeNode:
            if root1 is None:
                return None
            if root1 == target:
                return root2
            return dfs(root1.left, root2.left) or dfs(root1.right, root2.right)

        return dfs(original, cloned)

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree?: LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree is rated Easy on LeetCode.
What is the time complexity of LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree cover?: LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree is tagged Tree, Depth-First Search, Breadth-First Search and Binary Tree on LeetCode.