How to keep a value throughout a recursive function (kdtree problem)

Question

I programming Kdtrees with Python 3 and I have an issue with the function that is aimed to determined whether the node put in the arguments is in the Kdtree.

I use a recursive function but it returns None even when the point is present.

#I put the init to show you how the kdnode is made

class KdNode:

def __init__(self, point, dim, left_child, right_child):
   self.point = point;
   self.dim = dim;
   self.left_child = left_child;
   self.right_child = right_child;


def KdTree_present(kdnode,point_to_test):
    if kdnode == None:
        return
    else:

        KdTree_present(kdnode.left_child, point_to_test)
        KdTree_present(kdnode.right_child, point_to_test)
        if kdnode.point == point_to_test:

            return True


#Kdnode_example = [(150, 300), 1, [(200, 250), 0, None, None], [(325, 400), 0, None, None]]

Even the output of KdTree_present has to be True, it is always None.

Answer 1

What type is point? Remember that if you compare objects you will always get false unless they're in the same space of memory (they're pointing to the same object), refer to this question Compare object instances for equality by their attributes in Python

For == to work you would have to override the function __eq__ in point. Either create that function or change your condition to something like if knode.point.x == point_to_test.x and knode.point.y == point_to_test.y

Edit:

To add to your comment, there's indeed a problem with the recursion, it will go through all the children until it returns False since there's no more children, or return True if it founds it, whatever is faster, what you should do is this:

def KdTree_present(kdnode,point_to_test):
    if kdnode == None:
        return False
    if kdnode.point == point_to_test:
        return True 
    return KdTree_present(kdnode.left_child, point_to_test) or KdTree_present(kdnode.right_child, point_to_test)