Day 2 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.

Follow up: Solve the problem if repeated values on the tree are allowed.

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.

My Tests

Link to util code

import copy
from .util import TreeNode
from.Day2 import Solution

s = Solution()


def test_find_node():
    tree = TreeNode(7)
    tree.left = TreeNode(4)
    tree.right = TreeNode(3)
    tree.right.left = TreeNode(6)
    tree.right.right = TreeNode(19)

    original = tree
    clone = copy.deepcopy(tree)

    assert s.getTargetCopy(original, clone, tree.right).val == 3

My Solution

from .util import TreeNode


def search(tree: TreeNode, val: int) -> TreeNode:
    if tree.val == val:
        return tree

    if tree.left is not None:
        l = search(tree.left, val)
        if l is not None:
            return l
    if tree.right is not None:
        r = search(tree.right, val)
        if r is not None:
            return r
    return None


class Solution:
    def getTargetCopy(
        self, original: TreeNode, cloned: TreeNode, target: TreeNode
    ) -> TreeNode:
        return search(cloned, target.val)

Analysis

My Commentary

At first, I thought this one seemed a little bit too easy. I usually find most of the problems hard. Even the "easy" ones. I was a bit confused by the fact that we got the original tree. A search seemed to do the trick. I thought I got a solution pretty quickly and the analysis looked good but then I noticed the memory. I am apparently not doing good with memory usage at all.

I didn't have much time that day so I didn't get to work on a better solution or the follow-up question.

I can only assume we can use the original tree in some way to speed it up or maybe it's just my lack of python knowledge letting me down. I am bookmarking this one to come back to later.