Algorithms Problem Solving Series (23 Part Series)

This post is part of the Algorithms Problem Solving series.

## Problem Description

This is the Clone Binary Tree problem. The description looks like this:

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.

## Examples

```
Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Input: tree = [7], target = 7
Output: 7
Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4
Input: tree = [1,2,3,4,5,6,7,8,9,10], target = 5
Output: 5
Input: tree = [1,2,null,3], target = 2
Output: 2
```

## Solution

The idea of my solution was to traverse the tree, starting from the left to the right side of the tree. To trsverse a tree, we use a recursion. The base case of this recursion is when we find the target value in the cloned tree. When we find it, just return the cloned tree node.

As I said earlier, we start from the left side of the tree. If we find it, the result will be different than `None`

, so we just return the node reference. We do the same thing for the right side of the tree.

```
def get_target_copy(original, cloned, target):
if cloned.val == target.val:
return cloned
if cloned.left:
result = get_target_copy(original.left, cloned.left, target)
if result:
return result
if cloned.right:
result = get_target_copy(original.right, cloned.right, target)
if result:
return result
```

## Resources

- Learning Python: From Zero to Hero
- Algorithms Problem Solving Series
- Big-O Notation For Coding Interviews and Beyond
- Learn Python from Scratch
- Learn Object-Oriented Programming in Python
- Data Structures in Python: An Interview Refresher
- Data Structures and Algorithms in Python
- Data Structures for Coding Interviews in Python
- One Month Python Course

Algorithms Problem Solving Series (23 Part Series)

## Discussion