BST tree search easy leetcode

Question

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.

this is what i get for my code:

 class Solution:
     def searchBST(self, root: TreeNode, val: int) -> TreeNode:
         if root == None:
             return None
         elif root.val == val:
             return root
         elif root.val>val:
             root = self.searchBST(root.left,val)
         else:
             root = self.searchBST(root.right,val)

which seems to output None. but if replace the line

 root = self.searchBST(root.left,val)

with

 return self.searchBST(root.left,val)

same with root.right

then it works. I am not too good at recursion but how can we do

 return self.searchBST(root.left,val)

doesnt searchBST(..) return a TreeNode so dont we have to put the treenode in the variable root?

Answer 1

No as mentioned in question you need to return the node that matches the val.

In order to do that you have to return the address of the node if you find the value and None if does not.

Inorder to back propagate the value either the root address or Null(in case of not found) so you must return some address at every step.

If you are having problem with recursion go with the iterative traversal.

root iterativeSearch(struct Node* root, int key) 
{ 
    // Traverse untill root reaches to dead end 
    while (root != NULL) { 
        // pass right subtree as new tree 
        if (key > root->data) 
            root = root->right; 

        // pass left subtree as new tree 
        else if (key < root->data) 
            root = root->left; 
        else
            return root; // if the key is found return 1 
    } 
    return  Null; 
} 

Go to this for recursion visualisations:https://www.cs.usfca.edu/~galles/visualization/BST.html

Answer 2

You have to explicitly tell Python what you want the function to return. That's what you are doing with the return None and the return root lines.

The the left and right cases, you are only changing the local value of the parameter root, not changing anything outside of the scope of the function. No explicit return is the same as return None.

Replacing the two root = by return should indeed do the work.

Answer 3

class Solution(object):
def is_leaf(self,root):
        return root.left is None and root.right is None

def searchBST(self, root, val):

    if root is None:
        return root
    if self.is_leaf(root):
        if root.val == val:
            return root
        return None

    if root.val == val:
        return root
    elif val < root.val:
        return self.searchBST(root.left,val)
        
    else:
        return self.searchBST(root.right,val)