Table Of Contents
* 🤓 INTRODUCTION
* 0️⃣1️⃣ ABOUT BINARY SEARCH TREES
* ⭕ CREATE A NODE
* 🔎BINARY SEARCH TREE
* 🔍FIND AN ELEMENT
* 👨🏻‍💻CODE
* 🙏 THANK YOU

🤓 INTRODUCTION

Welcome, my dear hackers!🚀 Welcome to yet another blog article about elementary data structures.

If you missed the previous article where we describe the Binary trees, you can check it out right here:

Today, we will show how to implement the binary search tree. We will concentrate on the implementation with a bit of theoretical explanation in the beginning. 🚀

Please feel free to connect with me via Twitter, Instagram or LinkedIn

0️⃣1️⃣ ABOUT BINARY SEARCH TREES

Basic operations on a binary search tree take time proportional to the height of the tree. For a complete binary tree with n nodes, such operations run in the O(logn) worst-case time.
If the tree is a linear chain of n nodes, however, the same operations take O(n) worst-case time.
In practice, we can’t always guarantee that binary search trees are built randomly, but we can design variations of binary search trees with good guaranteed
worst-case performance on basic operations.

A binary search tree is organized, as the name suggests, in a binary tree, that we discussed in the previous chapter. There, we concluded that we can represent such a tree by a linked data structure in which each node is an object. In addition to a key and satellite data, each node contains attributes left, right and a pointer that points to the nodes corresponding to its left child, its right child, and its parent, respectively. So, if a child or the parent is missing, the appropriate attribute contains the value of NULL. The root node is the only node in the tree whose parent is NULL. The keys in a binary search tree are always stored in such a way as to satisfy the binary search tree property.

Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y:key <= x:key. If y is a node in the right subtree of x, then y:key >= x:key.

The binary-search-tree property allows us to print out all the keys in a binary search tree in sorted order by a simple recursive algorithm, called an inorder tree walk. This algorithm is so named because it prints the key of the root of a subtree between printing the values in its left subtree and printing those in its right subtree. (Similarly, a preorder tree walk prints the root before the values in either subtree and a postorder tree walk prints the root after the values in its subtrees.)

⭕ CREATE A NODE

As you can see in an image, we have a class BSTNode (Binary Search Tree Node) that has a constructor that takes up an argument of value being assigned to a member class variable value; Also, we have two pointers left and right, that will point to the left child and right child, respectively. The counter is used to control the duplication of the node values. For example, if we try to add another node with the same value as any node in a tree, we just increase the counter but do not add that node to the tree.

🔎 BINARY SEARCH TREE

🔍 FIND AN ELEMENT

👨🏻‍💻 CODE

class BSTNode {
  constructor(value) {
    this.value = value;
    this.right = null;
    this.left = null;
    this.count = 0;
  }
}

class BST {
  constructor() {
    this.root = null;
  }
  create(value) {
    const newNode = new BSTNode(value);
    if (!this.root) {
      this.root = newNode;
      return this;
    }

    let current = this.root;

    const addSide = side => {
      if (!current[side]) {
        current[side] = newNode;
        return this;
      }
      current = current[side];
    };

    while (true) {
      if (value === current.value) {
        current.count++;
        return this;
      }
      if (value < current.value) addSide('left');
      else addSide('right');
    }
  }
  find(value) {
    if (!this.root) 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 'Oops! Nothing found!';
    return current;
  }
}

let binary_search_tree = new BST();
binary_search_tree.create(100);
binary_search_tree.create(2);
binary_search_tree.create(21);
binary_search_tree.create(221);
binary_search_tree.create(3);
binary_search_tree.create(44);
console.log(binary_search_tree)

The expected output should be something like this:

🙏 THANK YOU FOR READING!

Stay tuned for the next chapter of this article where we will implement deletion and traversal logic!

References:
School notes...
School books...

Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me!

☕ SUPPORT ME AND KEEP ME FOCUSED!

Have a nice time hacking! 😊