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?
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