Finding a Node In a BST

In this article, we will discuss how to search for a node in a Binary Tree. The basic idea is to check whether a particular value is present in the tree or not, such as checking for the presence of number(50) or number(100). The search process is very similar to inserting a node in a Binary Search Tree, which we have already discussed in a previous article. If you are not familiar with Binary Search Trees, please refer to that article before proceeding with this one.

The fundamental principle of Binary Search Trees is that if a node is greater than the nodes in the tree, it will be placed on the right side of the tree, and if it is less, it will be placed on the left side. With each comparison that we make, we can discard about half of the tree.

For example, when we insert a number (3), the new node would be placed in the binary tree as shown in the diagram. Similarly, when searching for a node, we will follow the same path to find the desired node in a Binary Search Tree.

VisualGo Demonstration

To search for a node with the value of 50 in the binary search tree, we would start at the root node and compare the value of 50 to the value of the root node. If the value is less than the root node, we move to the left child node. If it is greater, we move to the right child node. We continue to do this comparison and movement until we either find the node with the value of 50 or we reach a null node, indicating that the value is not in the tree. We can visualize this process as a path of movements from the root node to the desired node or null node.

VisualGo Demonstration

Great, the pseudo code is a good outline of the steps needed to find a node in a binary search tree. Now we can use this as a guide to implement our function in code. Let’s start by defining a function called findNode that takes two arguments, node (the root node of the tree) and value (the value we are looking for):javascriptCopy code

function findNode(node, value) {
  // Pseudo code steps here
}

Inside the function, we can follow the steps outlined in the pseudo code. First, we check if there is a root node. If not, we can return false since the tree is empty and the value cannot be found:

function findNode(node, value) {
  if (!node) {
    return false;
  }
  // Pseudo code steps here
}

Next, we check if the value of the current node is the value we are looking for. If so, we can return true since we have found the node:

function findNode(node, value) {
  if (!node) {
    return false;
  }
  if (node.value === value) {
    return true;
  }
  // Pseudo code steps here
}

If the value is not found in the current node, we need to check if it is greater or less than the value of the current node. If it is greater, we recursively call the findNode function on the right child of the current node. If it is less, we recursively call the findNode function on the left child of the current node:

function findNode(node, value) {
  if (!node) {
    return false;
  }
  if (node.value === value) {
    return true;
  }
  if (value > node.value) {
    return findNode(node.right, value);
  } else {
    return findNode(node.left, value);
  }
}

Now our findNode function is complete and we can use it to find a specific value in a binary search tree.

Binary Search Trees (BSTs) are a popular data structure used in computer science for their efficient searching and sorting capabilities. In this article, we’ll go over how to implement a method to find a specific node in a BST using JavaScript.

First, we’ll create a Node class to represent each node in the BST. Each node will have a value, a reference to its left child node, and a reference to its right child node.

class Node {
  constructor(value) {
    this.value = value;
    this.right = null;
    this.left = null;
  }
}

Next, we’ll create a BinarySearchTree class to represent the BST. The BST will have a root node that we can use to traverse the tree.

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
}

To find a specific node in the BST, we’ll create a method called find that accepts a value and returns the node with that value. If the value is not found in the tree, the method will return undefined.

class BinarySearchTree {
  // ...
find(value) {
    if (this.root === null) return undefined;
    let current = this.root;
    let 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;
  }
}

Let’s break down the logic of our find method:

1. First, we check if the BST has a root node. If it doesn’t, we know the value isn’t in the tree, so we return undefined.
2. We create a variable called current and set it to the root node.
3. We create a variable called found and set it to false. This variable will keep track of whether or not we've found the node with the value we're looking for.
4. We use a while loop to traverse the BST. The loop continues as long as there is a current node and we haven't found the value we're looking for.
5. If the value we’re looking for is less than the current node’s value, we move to the left child node and update current accordingly.
6. If the value we’re looking for is greater than the current node’s value, we move to the right child node and update current accordingly.
7. If we find the node with the value we’re looking for, we set found to true.
8. Finally, we check if we found the node. If we didn’t, we return undefined. If we did, we return the current node.

If we don’t need to return the node with the value we’re looking for and only need to know if the value exists in the tree, we can create a simpler method called contains that returns true or false.

class BinarySearchTree {
  // ...

contains(value) {
    if (this.root === null) return false;
    let current = this.root;
    let 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;
  }
}