InOrder Traversal in Python
The problem I am facing is finding the first occurrence of a node in a workaround in BST. The code I am here 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 returns None, which is wrong with it. I think I will return a node when I find a node with a value of k. Why can't Python pass this node ??? thanks in advance
source to share
When you call yourself recursively, for example:
InOrder_search_recursive(node.lChild)
This is a normal function call just like any other. It just calls the function and returns the result. It is not automatically a return
value from this function or anything else.
So you search the left subtree, ignore the results, then keep checking node.value == key
, and if that fails, you search the right subtree, ignore the results again, and fall off the end of the function, that is, you return None
.
To make this work, you need return
to return a value. But, of course, only if it is not None
.
Also, you forgot to pass the argument key
before the recursive call, so you just get TypeError
. (I'm assuming your real code doesn't have this problem, but since you didn't show us your real code or 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 a validation not None
to search on the right side, because if it returns None
, we have nothing else to try and will just return None
anyway.)
source to share
Since your problem is to find the first occurrence node in its inorder traversal
, you should 1) traverse the tree in order and 2) stop when you find the first occurrence.
def search(node, key):
if node is None:
return None
# Search the left subtree and return early if key is found
n = search(node.lChild, key)
if n is not None:
return n
# Check middle and return early if key is found
if node.value == key:
return node
# Search right subtree
return search(node.rChild, key)
source to share
My other answer provides a beginner-friendly solution, but if you want a more powerful and concise answer:
def Inorder_search_recursive_all(node, key):
if not node:
return
yield from InOrder_search_recursive(node.lChild, key)
if node.value==key:
yield node
yield from InOrder_search_recursive(node.rChild, key)
This generates all the matches in the tree in order. And it gives them to you as an iterator, so if you just want the first one, you can stop as soon as you find it, without losing your work:
def Inorder_search_recursive(node, key):
return next(Inorder_search_recursive_all(node, key), None)
The Iterators section of the tutorial and the next Generators section explain how this works. The only missing bit is the explanation yield from
, which is explained in PEP 380 .
source to share