700. Search in a Binary Search Tree

Prompt

You’re given the node of a binary search tree (BST) and an integer , and your task is to find a node within the BST that has a value equivalent to . If there is a node that has a value equivalent to , then return the entire subtree with that node as the . Conversely, if there is no node that has a value equivalent to , then return .

Approach

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 node’s value and nodes in the right subtree contain values that are greater than the node’s value. Because the definition of a BST is recursive, this sorted property not only applies to the 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.

Base Case

The base case is simple as it would be a conditional statement checking if the node is . This is because the leaf level nodes in a BST technically still have a & pointer except that they are pointing to instead of a specific node. Therefore, if you were to imagine creating and using a pointer called 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 is equal to .

Recursive Step

At each level in the tree, we would want to compare the node that we are traversing with and see if the node’s value is either greater, smaller, or equal to .

If the node that we are currently traversing has a value that is greater than , 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 should be located somewhere in the left subtree.

Conversely, if the node that we are currently traversing has a value that is smaller than , 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 should be located somewhere in the right subtree.

Finally, if the node that we are currently traversing has a value that is equivalent to , 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 which would also return its left & right subtrees naturally as this is the inherent nature of a BST.

Code

Python

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.

Discord

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 cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com