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

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