Binary Search Tree

To understand what a binary search tree is, we should first go over the tree data structure.

Tree is a hierarchical or nonlinear data structure. It is a collection of elements, called nodes, that are linked to each other. Each node has two pieces of information: 1. the data value itself and 2. a pointer that references other nodes.

Each tree has a root node, which can have zero or more child nodes. The child nodes make the root node a parent node. Each of those child nodes could have their own child nodes and so on. It is therefore possible for a node to be both a child and a parent at the same time. Two child nodes that are next to each other are called siblings. Any node that does not have a child is a leaf.

A binary tree is a type of tree where each node has a maximum of 2 children.

A binary search tree is a type of a binary tree that naturally stays sorted because it follows this rule:

• Every left child always be less than its parent
• Every right child always be greater than its parent

BST is balanced when its left and right subtrees have roughly the same amount of nodes. Otherwise it will be unbalanced.

If the left and right side of a BST have exactly the same number of nodes, then it is a perfect tree, which is actually quite rare.

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

class BST {
  constructor(value) {
    this.root = new Node(value)
    this.count = 1
  }

  size() {
    return this.count
  }

  insert(value) {
    this.count++

    let newNode = new Node(value)

    const searchTree = node => {
      // if value < node.value, go left
      if (value < node.value) {
        // if no left child, append new node
        if (!node.left) {
          node.left = newNode
        } 
        // if left child, look left again
        else {
          searchTree(node.left)
        }
      }
      // if value > node.value, go right
      else if (value > node.value) {
        // if no right child, append new node
        if (!node.right) {
          node.right = newNode
        }
        // if right child, look right again
        else {
          searchTree(node.right)
        }
      }
    }

    searchTree(this.root)
  }
}