loading...
Cover image for Algorithms Problem Solving: Cloned Binary Tree

Algorithms Problem Solving: Cloned Binary Tree

teekay profile image TK Originally published at leandrotk.github.io ・2 min read

Algorithms Problem Solving Series (23 Part Series)

1) Algorithms Problem Solving: Jewels and Stones 2) Algorithms Problem Solving: Ransom Note 3 ... 21 3) Algorithms Problem Solving: Sum of nodes 4) Algorithms Problem Solving: Subtract product and sum 5) Algorithms Problem Solving: Cloned Binary Tree 6) Algorithms Problem Solving: Group the people 7) Algorithms Problem Solving: Equal Reversed Arrays 8) Algorithms Problem Solving: Even Number of Digits 9) Algorithms Problem Solving: Reduce to zero 10) Algorithms Problem Solving: Deepest Leaves Sum 11) Algorithms Problem Solving: Tree to greater sum 12) Algorithms Problem Solving: to Lower case 13) Algorithms Problem Solving: Balanced Strings 14) Algorithms Problem Solving: Number of students 15) Algorithms Problem Solving: Destination City 16) Algorithms Problem Solving: Maximum 69 Number 17) Algorithms Problem Solving: Shuffle the array 18) Algorithms Problem Solving: Insert into Binary Search Tree 19) Algorithms Problem Solving: Construct Binary Search Tree from Preorder Traversal 20) Algorithms Problem Solving: Odd in Matrix 21) Algorithms Problem Solving: Sort the Matrix Diagonally 22) Algorithms Problem Solving: Discount for prices 23) Algorithms Problem Solving: Running Array Sum

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

Algorithms Problem Solving Series (23 Part Series)

1) Algorithms Problem Solving: Jewels and Stones 2) Algorithms Problem Solving: Ransom Note 3 ... 21 3) Algorithms Problem Solving: Sum of nodes 4) Algorithms Problem Solving: Subtract product and sum 5) Algorithms Problem Solving: Cloned Binary Tree 6) Algorithms Problem Solving: Group the people 7) Algorithms Problem Solving: Equal Reversed Arrays 8) Algorithms Problem Solving: Even Number of Digits 9) Algorithms Problem Solving: Reduce to zero 10) Algorithms Problem Solving: Deepest Leaves Sum 11) Algorithms Problem Solving: Tree to greater sum 12) Algorithms Problem Solving: to Lower case 13) Algorithms Problem Solving: Balanced Strings 14) Algorithms Problem Solving: Number of students 15) Algorithms Problem Solving: Destination City 16) Algorithms Problem Solving: Maximum 69 Number 17) Algorithms Problem Solving: Shuffle the array 18) Algorithms Problem Solving: Insert into Binary Search Tree 19) Algorithms Problem Solving: Construct Binary Search Tree from Preorder Traversal 20) Algorithms Problem Solving: Odd in Matrix 21) Algorithms Problem Solving: Sort the Matrix Diagonally 22) Algorithms Problem Solving: Discount for prices 23) Algorithms Problem Solving: Running Array Sum

Posted on Jun 2 by:

teekay profile

TK

@teekay

Sharing knowledge https://leandrotk.github.io/tk

Discussion

markdown guide