I am solving a Binary search tree problem where we are given a target node, and want to return the node with value that's closest to this target in the BST. Here is my code: It is retuning 'None' for many of the test cases. But running through the code on paper, it should be working. It is because the

Why are the base cases for my BST not running when searching for a target node?

I am solving a Binary search tree problem where we are given a target node, and want to return the node with value that’s closest to this target in the BST.

Here is my code:

def findClosestValueInBst(tree, target):
    if target == tree.value: 
        return target
    if target<tree.value and not tree.left: 
        return tree.value 
    if not tree.right and target > tree.value: 
        return target 
    
    if target < tree.value: 
        findClosestValueInBst(tree.left, target)
    else: 
        findClosestValueInBst(tree.right, target)

It is retuning 'None' for many of the test cases. But running through the code on paper, it should be working.

It is because the base cases are not running in the case of if target<tree.value and not tree.left and if not tree.right and target > tree.value…

But any idea why it is not executing? – as I can’t seem to figure it out!

As an example:

For the following, I trace the tree down to node 13 with my code, then 13.left is None, so we should return tree.value, but this is not executing for some reason.

Answer

You forgot to add return statement for recursive calls. With the following part, it should work as expected.

if target < tree.value: 
    return findClosestValueInBst(tree.left, target)
return findClosestValueInBst(tree.right, target)

Advertisement

Answer