When you call yourself recursively, like this:
InOrder_search_recursive(node.lChild)
That's just a normal function call, like any other. It just calls the function and gets back a result. It doesn't automatically return
the value from that function, or do anything else.
So, you do the left-subtree search, ignore the results, then go on to check node.value == key
, and, if that fails, you do the right-subtree search, again ignore the results, and fall off the end of the function, meaning you return None
.
To make this work, you need to return
the value you got back. But, of course, only if it's not None
.
Also, you forgot to pass the key
argument down to the recursive call, so you're just going to get a TypeError
. (I'm guessing your real code doesn't have this problem, but since you didn't show us your real code, or a working example, I can't be sure…)
So:
def Inorder_search_recursive(node, key):
if not node:
return None
result = InOrder_search_recursive(node.lChild, key)
if result is not None:
return result
if node.value==key:
return node
return InOrder_search_recursive(node.rChild, key)
(You don't need the not None
check for the right-side search, because if it returns None
, we have nothing else to try and are just going to return None
anyway.)