lexie lexie - 6 months ago 24
Python Question

InOrder Traversal in Python

The problem I am tackle with is to find the first occurrence node in its inorder traversal in a BST.
The code I have is given below

def Inorder_search_recursive(node,key):
if not node:
return None
InOrder_search_recursive(node.lChild)
if node.value==key:
return node
InOrder_search_recursive(node.rChild)


This code always return None, what's wrong with it. I think I've return node when I find a node with value k. Why cannot python pass this node???Thanks in advance

Answer

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.)

Comments