I can't get the specific node of BST using recursion . i.e. every stack it erase

Question

global nodeM
nodeM=None
def inorderTraversal(self, root: 'TreeNode', tval:int) -> 'TreeNode':
    #if(nodeM):
        #print("sdf", type(nodeM))
        #node=None
    if root:
       
        self.inorderTraversal(root.left,tval)
        print(root.val)
        if(root.val==tval):

            #print("root = ",root)
            
            nodeM=root
            print("node = ", nodeM)
            print("my MAN,", type(nodeM))
            return nodeM
            return #node

            #inorderTraversal(root.left,tval)
        self.inorderTraversal(root.right,tval)
        
        return

This is the code every time I try to return the node. If it's the root, it works, otherwise it returns null-none. The problem is find the node with tval, it exist for sure.

Answer 1

There are a few issues:

• Although you have a return nodeM, you ignore this returned value when a recursive call has been made. You have self.inorderTraversal(root.left,tval), but don't do anything with what this call returns, yet that return could be the node that was found. The same goes for self.inorderTraversal(root.right,tval)

• Using a global variable is not helping, as there is no code that ever reads that value of nodeM (apart from printing it). Moreover, it is only set to None once, so that if you have multiple tree traversals, nodeM might still have a node reference from a previously iterated tree. So just don't use a global variable. It is not needed.

Corrected code with comments where changes were made:

class Solution:
    def inorderTraversal(self, root: 'TreeNode', tval:int) -> 'TreeNode':
        if root:
            result = self.inorderTraversal(root.left, tval)
            if result:  # Should check if the recursive call had success
                return result
            if root.val == tval:
                # Don't use a global variable: only return the match
                return root
            result = self.inorderTraversal(root.right,tval)
            if result:  # Should check if the recursive call had success
                return result

You could do this with one return expression too:

class Solution:
    def inorderTraversal(self, root: 'TreeNode', tval:int) -> 'TreeNode':
        return root and (
            root if root.val == tval else (
                self.inorderTraversal(root.left, tval) or
                self.inorderTraversal(root.right,tval)
            )
        )

One more remark: in the title of your post you mention "BST". This is confusing, because a full traversal is only necessary if your tree is just any binary tree, not necessarily a BST. If however your tree is a BST, then you should not perform an inorder traversal. The idea of a BST is that you have a faster way to find a node, and you don't have to look both left and right, but only go one way. If in fact you wanted to search a BST, then check out Search in a Binary Search Tree

Answer 2

As the detailed analysis of the issues with your code is given in the answer by trincot, this supplementary response tries to simplify the explanation and provides along with an example of binary tree to traverse also more details about the approach using the logical operators and and or which in Python don't return True/False as value but a value of one of the components of the expression.

The actual root of the issue you describe is to expect that the initial call of the traverse function will return you the found node except the case of the root node where there is no recursion. This does not work as expected because in your code the values returned by the deeper level recursion function calls simply go nowhere and don't propagate upwards to the calling function.

Notice that the code in your question always traverses the entire tree. I have adjusted it a bit to stop further search at the found node and solved also the issue of not returning the found node using a global variable, which is in my eyes a simpler to understand approach than smart usage of the return values as suggested by trincot.

Further explanations are provided as comments in the code below:

import collections

foundNode=None
def inorderTraversal1(node, tval):
    global foundNode
    if   node is not None   and   foundNode is None:
        print( node.val )
        if(node.val==tval):
            print("nodeValue = ", node.val)
            print("nodeType", type(node))
            foundNode=node
        else: # the node has other node.val as tval, so check its sub-nodes: 
            inorderTraversal1(node.left,tval)
            if foundNode is None: 
                inorderTraversal1(node.right,tval)  

def inorderTraversal2( root, tval ):
    return root and ( 
# NOTICE that logical   and   does not return True/False but the first component
#   which evaluates to False, or the last component if all evaluate to True
        root if root.val == tval else (
            inorderTraversal2(root.left, tval) 
            or
            inorderTraversal2(root.right,tval)
# NOTICE that logical   or   does not return True/False but the first item
#   which evaluates to True, or the last item if all evaluate to False
    )
)

BTnode = collections.namedtuple('BTnode', ['left', 'right', 'val'])
root=BTnode( val='0',
    left=BTnode( val='01',
        left=BTnode( val='011',
            left=BTnode( val='0111', left=None, right=None ),
            right=BTnode( val='0112',
                left=BTnode(val='01121', left=None, right=None ),
                right=BTnode( val='01122', left=None, right=None )
            )
        ),
        right=BTnode( val='012', left=None, right=None  )
    ),
    right=BTnode( val='02',
        left=BTnode( val='021', left=None, right=None ),
        right=BTnode( val='022', left=None,     right=None  )
    )
)

foundNode=None; inorderTraversal1(root, '022') # !!! WATCH OUT !!!
#        ^-- initialize `foundNode=None` in front of every call
#                of `inorderTraversal1()`
print(foundNode)
print( " ----- " )
print( inorderTraversal2(root, '022') )
print("===============")
foundNode=None; inorderTraversal1(root, '01122')
print(foundNode)
print( " ----- " )
print( inorderTraversal2(root, '01122') )

which outputs:

> cd /home/o/oOo/O@@/stackoverflow
> python3 -u "BTree.py"
0
01
011
0111
0112
01121
01122
012
02
021
022
nodeValue =  022
nodeType <class '__main__.BTnode'>
BTnode(left=None, right=None, val='022')
 ----- 
BTnode(left=None, right=None, val='022')
===============
0
01
011
0111
0112
01121
01122
nodeValue =  01122
nodeType <class '__main__.BTnode'>
BTnode(left=None, right=None, val='01122')
 ----- 
BTnode(left=None, right=None, val='01122')
> exit status: 0