Trees, Tries and Graphs

Binary Search Trees

const Node = function(value) {
  this.value = value
  this.left = null
  this.right = null
}

const BST = function() {
  this.head = null
  this.count = 0
}

BST.prototype.insert(value, node = head) {
    // see below
}

BST.prototype.remove(value, node = head) {
    // see below
}

Insertion

• Time complexity O( h ), where h is the height of the tree
• Simple, just iterate down the tree, when you get to a node with 2 null legs, insert into proper leg

BST.prototype.insert = function(value, node = head) {
  if(value === node.value) {
    throw 'value already in tree'
  } else {

    if(value > node.value) {

      if(node.right === null) {
        node.right = new Node(value)
      } else {
        this.insert(value, node.right)
      }

    } else {

      if(node.left === null) {
        node.left = new Node(value)
      } else {
        this.insert(value, node.left)
      }

    }
  }
}

Removal

• This gets a little more complicated, there are multiple cases for deletion

• If the node is a leaf, simply remove it

• If the node has children, you must iterate down once(left or right) and then all the way to the leaf only going the opposite direction

BST.prototype.remove = function(value) {

  if(value === this.head.value) {

    let iter = null

    // if there is a left branch whend
    if(this.head.left) {
      iter = this.head.left
      while(iter.right) {
        iter = iter.right
      }
      this.head = iter

    } else if(this.head.right) {
      iter = this.head.right
      while(iter.left) {
        iter = iter.left
      }
      this.head = iter
    } else {
      this.head = null
    }

  } else {
    findAndRemove(value, this.head)
  }
}

// --------- helper function
const findAndRemove = function(val, node) {

  let side = val < node.value ? 'left' : 'right'
  let next = node[side]

  if(next) {

    if(val !== next.value) {
      findAndRemove(val, next)
    } else {

      // Value to remove has 2 children
      if(next.left && next.right) {
        let iter = next.left
        while(iter.right !== null) {
          iter = iter.right
        }
        node[side] = iter

      // Value to remove has no children  
      } else if (!next.left && !next.right){
        node[side] = null

      // value to remove has 1 child
      } else {
        node[side] = (next.left) ? next.left : next.right
      } 
    }
  }
}

Trie

• Tries are useful especially for strings since they have a retrieval time complexity of O(t) where t is the length of a string.

• Uses

• Autocomplete text

• Phone number lookup

• Spell checkers
• Finding a