Finding a Node In a BST

We will talk about how to find or search a node in a Binary Tree in this article. Basically the idea is that When you have a binary tree you can search to see if a value is in that tree. We could search to see if number(50) is in the tree or number(100) is in the tree. Process is very similar to inserting in a Binary Search Tree which I already wrote an article about it. If you are not familiar with the Binary search tree, you can read an article before you start in this article.

The idea of Binary search tree is, If the node is greater than the nodes from the tree, it will go and place right of the tree. If the node is less than the nodes from the tree, it will be placed on the left side of the tree. We can cut about half the tree away each comparison that we make.

For Example

When we go to insert a number (3). You can see on diagram how the new node would be replaced on our binary tree as follows. If we go to search a node, it will follow the same path to find a desired node in a BST.

We will use a true or false statement in our code to see if we found a node in BST. If it contains that value which we are looking for or not. If the value is not in the tree it will tell us the value is not there.

Let’s see if we search number (50) How can we visualize it?

As you can see the number that we are looking for (50) is greater than the root(first node) So we are going to check the right side of the node and see as visualize above. Those are the basic steps . We will dive in and see how we can implement a function to find a value in the BST now. Lets see which steps we should follow on our Pseudo code to implement our method to find the desirable node.

Pseudo code for Finding a Node in BST

  • Starting at the root
  • Check if there is a root, if not — we’re done searching!
  • If there is a root, check if the value of the new node is the value we are looking for. If we found it, we’re done!
  • If not, check to see if the value is greater than or less than the value of the root
  • If it is greater
  • Check to see if there is a node to the right
  • If there is, move to that node and repeat these steps
  • If there is not, we’re done searching!
  • If it is less
  • Check to see if there is a node to the left
  • If there is, move to that node and repeat these steps
  • If there is not, we’re done searching!
class Node {     constructor(value){     this.value = value;     this.right = null;     this.left = null;    }} class BinarySearchTree{    constructor(){       this.root = null;   }
find(value){
if (this.root === null) return false;
var current = this.root,
found = false;
while(current && !found){
if(value < current.value){
current = current.left;
} else if(value > current.value){
current = current.right;
} else {
found = true
}
}
}
if(!found) return undefined;
return current
}

Breaking down our code

1- Let’s find our best class. First thing we added the method to find and accept a value and we have a couple of optimization we can make at the end. We will check if there is a root?

find(value){if(this.root === null) return false;

2- We created a variable called current and set it to the root.

var current = this.root;

3- We created a variable called found and set it to false. Found is keeping track of the item we found.

var found = false

4- Then we need to get the bulk of our logic which involves looping. We use a while loop for this function. While we have not found the thing, but also while there is a current. Also while there is a current. If we never find it, found would always be false. We also need to be sure we should get out of the loop at the same point. Current would be our value, when there is no current while we are looping our tree then our loop will stop.

while(current && !found )

5- If the value is less than current then we will set current to do left as follows..

current = current.left;

6- We created another statement else if . If the value is greater than the current value. If the case true current is set up current.right . Here is the implementation of the else if statement as follows.

} else if(value > current.value){
current = current.right;

7- If we found the node, We set up found variable to the true..

found = true

As you see we implemented our function for each case with statements to get out of the loop as above.

7- The last thing we should do is return the current but we set up our return just in case if we don’t find anything in BTS.

if(!found) return undefined;
return current

True & false Version

If we want to return just true and false version the function above. We can make some small changes and we can implement as follows. It’s not return nodes if it’s true or false.

contains (value){
if (this.root === null) return false;
var current = this.root,
found = false;
while(current && !found){
if(value < current.value){
current = current.left;
} else if(value > current.value){
current = current.right;
} else {
return true
}
}
}

return false
}

As you see I implemented two functions, first is returning the node which we are looking for, another is returning if the node is in the BTS and returning it with true and false. The binary tree is one of the more useful of the “advanced” data structures and it is fairly easy to implement in JavaScript..

However the usual method is to use object references, links or pointers and this makes searching the tree an expensive task. To find a given node in the tree you generally have to traverse the tree and examine all the nodes on the way to the target node.

Software Engineer | Ruby on Rails | JavaScript | HTML5 | CSS | PostgreSQL | React | Redux