700. Search in a Binary Search Tree
Leetcode #: 700
Name: Search in a Binary Search Tree
Companies asked: Amazon, Google, Meta, Microsoft, Salesforce
You’re given the root node of a binary search tree (BST) and an integer val, and your task is to find a node within the BST that has a value equivalent to val. If there is a node that has a value equivalent to val, then return the entire subtree with that node as the root. Conversely, if there is no node that has a value equivalent to val, then return null.
To solve this problem, it’s essential that you understand the inherent nature behind a binary search tree (BST). A BST as opposed to a regular binary tree is sorted in a specified order in which nodes in the left subtree contain values that are less than the root node’s value and nodes in the right subtree contain values that are greater than the root node’s value. Because the definition of a BST is recursive, this sorted property not only applies to the root level node but also in each and every level of the BST.
Though the code could be written iteratively, it’s recommended to write it recursively in this case because it’s more convenient due to the recursive nature of a BST. Just like in any other recursive function, we will need to define 2 parts: the base case & the recursive step.
The base case is simple as it would be a conditional statement checking if the root node is null. This is because the leaf level nodes in a BST technically still have a left & right pointer except that they are pointing to null instead of a specific node. Therefore, if you were to imagine creating and using a pointer called current traversing through each node level-by-level in the BST, then we would know to stop iterating the BST (if we’ve reached the end of the BST) once current is equal to null.
At each level in the tree, we would want to compare the node that we are traversing with val and see if the node’s value is either greater, smaller, or equal to val.
If the node that we are currently traversing has a value that is greater than val, then we know that we should recursively call and return the function with root.left because we can deduce that a node with value of val should be located somewhere in the left subtree.
Conversely, if the node that we are currently traversing has a value that is smaller than val, then we know that we should recursively call and return the function with root.right because we can deduce that a node with value of val should be located somewhere in the right subtree.
Finally, if the node that we are currently traversing has a value that is equivalent to val, then we can simply return that node because that is what the problem is asking for us to return. Because each node is connected by left & right pointers by default, we can simply return that node with a value equivalent to val which would also return its left & right subtrees naturally as this is the inherent nature of a BST.
Thank you for reading!
In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.
If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at email@example.com