Search code examples
python-3.xalgorithmtreebinary-treetraversal

Why is this binary tree preorder traversal returning none

Hi I am attempting to solve leetcode problem 1379.

Here is the statement of the problem + link:

https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/

Problem

Here is my failed attempt at a solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        if cloned:
            if cloned.val == target.val:
                return cloned
            self.getTargetCopy(original, cloned.left, target)
            self.getTargetCopy(original, cloned.right, target)

I am failing to understand why this is not working.

I think my solution is doing a preorder traversal of the tree and at each stage asking if the node in the cloned tree exists and if so is it's value equal to the value we are looking for? If it is then return that node and we have found the one we are looking for.

If not then check simply carry on checking the tree. Since the values in the tree are guaranteed to be unique and the target value is guaranteed to be in the tree then and I am visiting every node then surely this must work at finding the answer.

However it is failing the automated tests, it doesn't even pass the example 1 (pictured above) and is saying it is returning null.

What am I missing?

EDIT:

I tried printing my original solution with the arguements at each function call:

__main__.Solution.getTargetCopy ( self = <__main__.Solution object at 0x000002B15CF31358>, original = 7, cloned = 7, target = 3 )
__main__.Solution.getTargetCopy ( self = <__main__.Solution object at 0x000002B15CF31358>, original = 7, cloned = 4, target = 3 )
__main__.Solution.getTargetCopy ( self = <__main__.Solution object at 0x000002B15CF31358>, original = 7, cloned = None, target = 3 )
__main__.Solution.getTargetCopy ( self = <__main__.Solution object at 0x000002B15CF31358>, original = 7, cloned = None, target = 3 )
__main__.Solution.getTargetCopy ( self = <__main__.Solution object at 0x000002B15CF31358>, original = 7, cloned = 3, target = 3 )
None

So as well can see the cloned tree traverses from 7 down to 4 then checks 4's left and right child which are both none, then it checks 7's right child 3 and confirms that it is the same as the target, at this point in the call cloned.val=3 so the return statement should return the node whose value is 3 which should be the right answer yet it seems to be returning none which is not even the value of cloned at that time (as proven by the print statement showing the arguments) what is going on?

Solution

  • When the if condition is not true, you don't return anything.

    So change these two lines:

    self.getTargetCopy(original, cloned.left, target)
self.getTargetCopy(original, cloned.right, target)

    To:

    res = self.getTargetCopy(original, cloned.left, target)
if res:
    return res
return self.getTargetCopy(original, cloned.right, target)

    Or even (using short circuit):

    return (self.getTargetCopy(original, cloned.left, target)
     or self.getTargetCopy(original, cloned.right, target))