## DEV Community is a community of 800,290 amazing developers

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

TK

Posted on • Originally published at leandrotk.github.io

# Algorithms Problem Solving: Cloned Binary Tree

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