The BVG Software website is 🚧 UNDER CONSTRUCTION 🚧

Blog.

Simple Binary Search Tree

Cover Image for Simple Binary Search Tree
BVG Software
2 Min Read

Search of 100 Items

Search of 10000 Items

Binary Search Tree

This visualization is a Binary Search Tree I built using JavaScript. As values are added to the Binary Search Tree new nodes are created. Each node has a value, as well as a left and a right property. The left and right properties are other nodes in the tree that are connected to the current node.

The only rule of the Binary Search Tree is that the left node's value must be less than or equal to the parent node's value and the right node's value must be greater than or equal to the parent's value. This rule makes finding a value more efficient than the linear search alternative. Imagine a linear search as an array being checking one value at a time sequencially.

Big O Notation

Using Big O notation, the time complexity of a linear search is O(n), while the Binary Search Tree is O(log n). Essentially, the worst case scenario for a linear search is that every item in the array must be visited. This means the search time increases at the same rate that the size of the array increases. On the other hand, as the size of a Binary Search Tree increases the search time levels off. Simply stated, the more stuff being searched through, the more beneficial a Binary Search Tree becomes.

JavaScript Classes

Here are the JavaScript classes I used for this visualization

Binary Search Tree

class BinarySearchTree {
  constructor() {
    this.root = null
    this.path = []
  }

  insert(value) {
    var newNode = new Node(value)

    if (this.root === null) {
      this.root = newNode
    } else {
      this.insertNode(this.root, newNode)
    }
  }

  insertNode(node, newNode) {
    if (newNode.value < node.value) {
      if (node.left === null) {
        node.left = newNode
      } else {
        this.insertNode(node.left, newNode)
      }
    } else {
      if (node.right === null) {
        node.right = newNode
      } else {
        this.insertNode(node.right, newNode)
      }
    }
  }

  remove(value) {
    this.root = this.removeNode(this.root, value)
  }

  removeNode(node, key) {
    if (node === null) {
      return null
    } else if (key < node.value) {
      node.left = this.removeNode(node.left, key)
      return node
    } else if (key > node.value) {
      node.right = this.removeNode(node.right, key)
      return node
    } else {
      if (node.left === null && node.right === null) {
        node = null
        return node
      }
      if (node.left === null) {
        node = node.right
        return node
      } else if (node.right === null) {
        node = node.left
        return node
      }
      var aux = this.findMinNode(node.right)
      node.value = aux.value
      node.right = this.removeNode(node.right, aux.value)
      return node
    }
  }

  findMinMode(node) {
    if (node.left === null) {
      return node
    } else {
      return this.findMinNode(node.left)
    }
  }

  getRootNode() {
    return this.root
  }

  inorder(node) {
    if (node !== null) {
      this.inorder(node.left)
      console.log(node.value)
      this.inorder(node.right)
    }
  }

  search(node, value, initial = false) {
    if (initial) {
      this.path = []
    }
    if (node === null) {
      return null
    } else if (value < node.value) {
      this.path.push(node.value)
      return this.search(node.left, value)
    } else if (value > node.value) {
      this.path.push(node.value)
      return this.search(node.right, value)
    } else {
      this.path.push(node.value)
      return node
    }
  }

  getPath() {
    return this.path
  }

  getSearchPath(value) {
    this.search(this.root, value, true)
    return this.getPath()
  }
}

Node

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

Check out the source code at Observable.