Algorithms Problem Solving: Cloned Binary Tree
Tags: algorithms, python, computerscience, interview
Published: 2020-06-02 10:44:30

---
title: Algorithms Problem Solving: Cloned Binary Tree
published: true
description: Solving algorithms problems with TK
tags: algorithms, python, computerscience, interview
cover_image: https://raw.githubusercontent.com/leandrotk/tk/master/series/algorithms-problem-solving/assets/two-trees.jpg
canonical_url: https://leandrotk.github.io/tk/series/algorithms-problem-solving/cloned-binary-tree.html
series: Algorithms Problem Solving Series
---

This post is part of the [Algorithms Problem Solving](https://leandrotk.github.io/tk/series/algorithms-problem-solving/index.html) series.

## Problem Description

This is the [Clone Binary Tree](https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-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

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

```python
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](https://leandrotk.github.io/tk/2017/09/learning-python-from-zero-to-hero/index.html)
- [Algorithms Problem Solving Series](https://leandrotk.github.io/tk/series/algorithms-problem-solving/index.html)
- [Big-O Notation For Coding Interviews and Beyond](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond?aff=x8bV)
- [Learn Python from Scratch](https://www.educative.io/courses/learn-python-from-scratch?aff=x8bV)
- [Learn Object-Oriented Programming in Python](https://www.educative.io/courses/learn-object-oriented-programming-in-python?aff=x8bV)
- [Data Structures in Python: An Interview Refresher](https://www.educative.io/courses/data-structures-in-python-an-interview-refresher?aff=x8bV)
- [Data Structures and Algorithms in Python](https://www.educative.io/courses/ds-and-algorithms-in-python?aff=x8bV)
- [Data Structures for Coding Interviews in Python](https://www.educative.io/courses/data-structures-coding-interviews-python?aff=x8bV)
- [One Month Python Course](https://mbsy.co/lG6tv)