## DEV Community is a community of 870,143 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# 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

``````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. 