How to Find a Value in a BST? by Danny Reina

Difficulty: Easy

Intent

This article is meant to go hand in hand with my previous article on how to add a value to a binary search tree which can be found here. The objective of this article is to show you how to find a value in a BST. Let’s make this quick shall we.

Code

As in our last solution to inserting a value into a BST, we will be traversing our BST via iteration so at the very least we can start out with some very basic code.

Start traversing BST via iteration

Eventually, we have to find a node that matches the value we are passing into the find function right, so we need a condition that compares the value of the current node we are at to the value being pass. We can do so with this code.

Return node that matches the value being passed

Great, our function can now return a node that matches the value being passed into the function. But what if the first node we visit, which is always the root node in a BST, isn’t a match? Then we have to move the position of our current node to another node but which one? Remember the properties of a BST, all nodes to the right of the root node have greater values, all nodes to the left of the root node have lesser values. So if the value being passed is greater than the current node then we have to reassign our currentNode to the immediately next node on the right branch. If the value being passed is less than currentNode then we have to move the current node to the left branch of the current node we are currently positioned on.

Code to find a value in a BST

If you wish to get an even better understanding of the code, please click on the click to enlarge it to better read the comments I made on the code. Otherwise, feel free to contact me via my Linkedin to ask for further clarification.

Next Steps

We are approaching the final basic requirement of constructing a BST which is the remove method. At first, it may seem a bit overwhelming to grasp on the first attempt and that is completely okay, but I will break down the problem into smaller more consumable bits that will allow you to retain the information better. Stay tuned and happy coding!