JavaScript DSA From Scratch — Implementations & Handwritten Traces

function fibonacci(n) {
  const fib = [0, 1]
  if (n === undefined) return []
  if (n === 1) return [0]
  if (n === 2) return fib
 
  for (let i = 2; i < n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2]
  }
  return fib
}

fibonacci() // → []
fibonacci(1) // → [0]
fibonacci(2) // → [0, 1]
fibonacci(3) // → [0, 1, 1]
fibonacci(7) // → [0, 1, 1, 2, 3, 5, 8]

function factorial(n) {
  let result = 1
  if (n === 0) return 1
  if (n === 1) return 1
 
  for (let i = 2; i <= n; i++) {
    result = result * i
  }
  return result
}

factorial(0) // → 1
factorial(1) // → 1
factorial(5) // → 120

function isPrime(n) {
  if (n < 2) return false
 
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) return false
  }
  return true
}

isPrime(1) // → false
isPrime(3) // → true
isPrime(4) // → false
isPrime(5) // → true
isPrime(10) // → false
isPrime(10000) // → false
isPrime(235) // → false  (5 × 47)

function isPowerOfTwo(n) {
  if (n < 1) return false
 
  while (n > 1) {
    if (n % 2 !== 0) return false
    n = n / 2
  }
  return true
}

isPowerOfTwo(1) // → true
isPowerOfTwo(2) // → true
isPowerOfTwo(4) // → true
isPowerOfTwo(6) // → false
isPowerOfTwo(8) // → true

function isPowerOfTwoBitwise(n) {
  if (n < 1) return false
  return (n & (n - 1)) === 0
}

function recursiveFibonacci(n) {
  if (n < 2) return n
  return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2)
}

recursiveFibonacci(4)
├─ recursiveFibonacci(3)
│  ├─ recursiveFibonacci(2)
│  │  ├─ recursiveFibonacci(1) → 1
│  │  └─ recursiveFibonacci(0) → 0
│  │  → 1
│  └─ recursiveFibonacci(1) → 1
│  → 2
└─ recursiveFibonacci(2)
   ├─ recursiveFibonacci(1) → 1
   └─ recursiveFibonacci(0) → 0
   → 1

recursiveFibonacci(0) // → 0
recursiveFibonacci(1) // → 1
recursiveFibonacci(6) // → 8

function recursiveFactorial(n) {
  if (n === 0) return 1
  return n * recursiveFactorial(n - 1)
}

recursiveFactorial(4)
├─ recursiveFactorial(3)
│  ├─ recursiveFactorial(2)
│  │  ├─ recursiveFactorial(1)
│  │  │  └─ recursiveFactorial(0) → 1
│  │  │  → 1 * 1 = 1
│  │  └─ 2 * 1 = 2
│  └─ 3 * 2 = 6
└─ 4 * 6 = 24

recursiveFactorial(0) // → 1
recursiveFactorial(1) // → 1
recursiveFactorial(5) // → 120

function recursiveBinarySearch(arr, target) {
  return search(arr, target, 0, arr.length - 1)
}
 
function search(arr, target, leftIndex, rightIndex) {
  if (leftIndex > rightIndex) return -1
 
  const middleIndex = Math.floor((leftIndex + rightIndex) / 2)
 
  if (target === arr[middleIndex]) return middleIndex
  if (target < arr[middleIndex]) {
    return search(arr, target, leftIndex, middleIndex - 1)
  }
  return search(arr, target, middleIndex + 1, rightIndex)
}

recursiveBinarySearch([-5, 2, 4, 6, 10], 10) // → 4
recursiveBinarySearch([-5, 2, 4, 6, 10], 6) // → 3
recursiveBinarySearch([-5, 2, 4, 6, 10], 20) // → -1

function towerOfHanoi(n, fromRod, toRod, usingRod) {
  if (n === 1) {
    console.log(`Move disk 1 from ${fromRod} to ${toRod}`)
    return
  }
 
  towerOfHanoi(n - 1, fromRod, usingRod, toRod)
  console.log(`Move disk ${n} from ${fromRod} to ${toRod}`)
  towerOfHanoi(n - 1, usingRod, toRod, fromRod)
}

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i
  }
  return -1
}

linearSearch([-5, 2, 10, 4, 6], 10) // → 2
linearSearch([-5, 2, 10, 4, 6], 6) // → 4
linearSearch([-5, 2, 10, 4, 6], 20) // → -1

function binarySearch(arr, target) {
  let leftIndex = 0
  let rightIndex = arr.length - 1
 
  while (leftIndex <= rightIndex) {
    const middleIndex = Math.floor((leftIndex + rightIndex) / 2)
 
    if (arr[middleIndex] === target) return middleIndex
    if (target < arr[middleIndex]) {
      rightIndex = middleIndex - 1
    } else {
      leftIndex = middleIndex + 1
    }
  }
  return -1
}

binarySearch([-5, 2, 4, 6, 10], 10) // → 4
binarySearch([-5, 2, 4, 6, 10], 6) // → 3
binarySearch([-5, 2, 4, 6, 10], 20) // → -1

function bubbleSort(arr) {
  let swapped
  do {
    swapped = false
    for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        const temp = arr[i]
        arr[i] = arr[i + 1]
        arr[i + 1] = temp
        swapped = true
      }
    }
  } while (swapped)
}

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const numberToInsert = arr[i]
    let j = i - 1
 
    while (j >= 0 && arr[j] > numberToInsert) {
      arr[j + 1] = arr[j]
      j = j - 1
    }
    arr[j + 1] = numberToInsert
  }
}

function mergeSort(arr) {
  if (arr.length < 2) return arr
 
  const mid = Math.floor(arr.length / 2)
  const leftArr = arr.slice(0, mid)
  const rightArr = arr.slice(mid)
  return merge(mergeSort(leftArr), mergeSort(rightArr))
}
 
function merge(leftArr, rightArr) {
  const sortedArr = []
  while (leftArr.length && rightArr.length) {
    if (leftArr[0] <= rightArr[0]) sortedArr.push(leftArr.shift())
    else sortedArr.push(rightArr.shift())
  }
  return [...sortedArr, ...leftArr, ...rightArr]
}

function quickSort(arr) {
  if (arr.length < 2) return arr
 
  const pivot = arr[arr.length - 1]
  const left = []
  const right = []
 
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) left.push(arr[i])
    else right.push(arr[i])
  }
  return [...quickSort(left), pivot, ...quickSort(right)]
}

function cartesianProduct(arr1, arr2) {
  const result = []
  for (let i = 0; i < arr1.length; i++) {
    for (let j = 0; j < arr2.length; j++) {
      result.push([arr1[i], arr2[j]])
    }
  }
  return result
}

function climbingStaircase(n) {
  const noOfWays = [1, 2]
  for (let i = 2; i <= n; i++) {
    noOfWays[i] = noOfWays[i - 1] + noOfWays[i - 2]
  }
  return noOfWays[n - 1]
}

climbingStaircase(1) // → 1
climbingStaircase(2) // → 2
climbingStaircase(3) // → 3
climbingStaircase(4) // → 5
climbingStaircase(5) // → 8

class Stack {
  constructor() {
    this.arr = []
  }
 
  push(value) {
    this.arr.push(value)
    return this.arr
  }
 
  pop() {
    this.arr.pop()
    return this.arr
  }
 
  lookup() {
    return this.arr[this.arr.length - 1]
  }
}

class Stack {
  constructor() {
    this.database = {}
    this.count = 0
  }
 
  push(value) {
    this.count++
    this.database[this.count] = value
    return this.database
  }
 
  pop() {
    delete this.database[this.count]
    this.count--
    return this.database
  }
 
  peek() {
    return this.database[this.count]
  }
}

class LinkedListStack {
  constructor() {
    this.list = new LinkedList() // head + tail
  }
 
  push(value) {
    this.list.prepend(value) // O(1)
  }
 
  pop() {
    return this.list.removeFromEnd() // O(n) — suboptimal
  }
 
  peek() {
    return this.list.head.value
  }
}

class Queue {
  constructor() {
    this.items = []
  }
 
  enqueue(element) {
    this.items.push(element)
  }
 
  dequeue() {
    return this.items.shift()
  }
 
  isEmpty() {
    return this.items.length === 0
  }
 
  peek() {
    return this.isEmpty() ? null : this.items[0]
  }
 
  size() {
    return this.items.length
  }
}

class Queue {
  constructor() {
    this.items = {}
    this.rear = 0
    this.front = 0
  }
 
  enqueue(element) {
    this.items[this.rear] = element
    this.rear++
  }
 
  dequeue() {
    const item = this.items[this.front]
    delete this.items[this.front]
    this.front++
    return item
  }
 
  isEmpty() {
    return this.rear - this.front === 0
  }
 
  peek() {
    return this.items[this.front]
  }
 
  size() {
    return this.rear - this.front
  }
}

class CircularQueue {
  constructor(capacity) {
    this.items = new Array(capacity)
    this.capacity = capacity
    this.currentLength = 0
    this.rear = -1
    this.front = -1
  }
 
  isFull() {
    return this.currentLength === this.capacity
  }
 
  isEmpty() {
    return this.currentLength === 0
  }
 
  enqueue(element) {
    if (this.isFull()) return
    this.rear = (this.rear + 1) % this.capacity
    this.items[this.rear] = element
    this.currentLength += 1
    if (this.front === -1) this.front = this.rear
  }
 
  dequeue() {
    if (this.isEmpty()) return null
    const item = this.items[this.front]
    this.items[this.front] = null
    this.front = (this.front + 1) % this.capacity
    this.currentLength -= 1
    if (this.isEmpty()) {
      this.front = -1
      this.rear = -1
    }
    return item
  }
}

class LinkedListQueue {
  constructor() {
    this.list = new LinkedList()
  }
 
  enqueue(value) {
    this.list.append(value) // O(n) without tail
  }
 
  dequeue() {
    return this.list.removeFromFront() // O(1)
  }
 
  peek() {
    return this.list.head.value
  }
}

class Node {
  constructor(value) {
    this.value = value
    this.next = null
  }
}
 
class LinkedList {
  constructor() {
    this.head = null
    this.size = 0
  }
 
  prepend(value) {
    const node = new Node(value)
    if (!this.isEmpty()) node.next = this.head
    this.head = node
    this.size++
  }
 
  insert(value, index) {
    if (index < 0 || index > this.size) return
    if (index === 0) return this.prepend(value)
 
    const node = new Node(value)
    let prev = this.head
    for (let i = 0; i < index - 1; i++) prev = prev.next
    node.next = prev.next
    prev.next = node
    this.size++
  }
 
  reverse() {
    let prev = null
    let curr = this.head
    while (curr) {
      const next = curr.next
      curr.next = prev
      prev = curr
      curr = next
    }
    this.head = prev
  }
}

class LinkedList {
  constructor() {
    this.head = null
    this.tail = null
    this.size = 0
  }
 
  prepend(value) {
    const node = new Node(value)
    if (this.isEmpty()) {
      this.head = node
      this.tail = node
    } else {
      node.next = this.head
      this.head = node
    }
    this.size++
  }
 
  append(value) {
    const node = new Node(value)
    if (this.isEmpty()) {
      this.head = node
      this.tail = node
    } else {
      this.tail.next = node
      this.tail = node
    }
    this.size++
  }
 
  removeFromFront() {
    if (this.isEmpty()) return null
    const value = this.head.value
    this.head = this.head.next
    this.size--
    return value
  }
 
  removeFromEnd() {
    if (this.isEmpty()) return null
    const value = this.tail.value
    if (this.size === 1) {
      this.head = null
      this.tail = null
    } else {
      let prev = this.head
      while (prev.next !== this.tail) prev = prev.next
      prev.next = null
      this.tail = prev
    }
    this.size--
    return value
  }
}

class Node {
  constructor(value) {
    this.value = value
    this.next = null
    this.prev = null
  }
}
 
class DoublyLinkedList {
  constructor() {
    this.head = null
    this.tail = null
    this.length = 0
  }
 
  push(value) {
    const newNode = new Node(value)
    if (!this.head) {
      this.head = newNode
      this.tail = newNode
    } else {
      this.tail.next = newNode
      newNode.prev = this.tail
      this.tail = newNode
    }
    this.length++
    return this
  }
 
  pop() {
    if (!this.head) return null
    const popped = this.tail
    if (this.length === 1) {
      this.head = null
      this.tail = null
    } else {
      this.tail = popped.prev
      this.tail.next = null
      popped.prev = null
    }
    this.length--
    return popped
  }
 
  unshift(value) {
    const newNode = new Node(value)
    if (!this.head) {
      this.head = newNode
      this.tail = newNode
    } else {
      newNode.next = this.head
      this.head.prev = newNode
      this.head = newNode
    }
    this.length++
    return newNode
  }
 
  shift() {
    if (!this.head) return null
    const oldHead = this.head
    if (this.length === 1) {
      this.head = null
      this.tail = null
    } else {
      this.head = oldHead.next
      oldHead.next = null
      this.head.prev = null
    }
    this.length--
    return oldHead
  }
}

class HashTable {
  constructor(size) {
    this.table = new Array(size)
    this.size = size
  }
 
  hash(key) {
    let total = 0
    for (let i = 0; i < key.length; i++) total += key.charCodeAt(i)
    return total % this.size
  }
 
  set(key, value) {
    const index = this.hash(key)
    const bucket = this.table[index]
    if (!bucket) {
      this.table[index] = [[key, value]]
      return
    }
    const sameKeyItem = bucket.find((item) => item[0] === key)
    if (sameKeyItem) sameKeyItem[1] = value
    else bucket.push([key, value])
  }
 
  get(key) {
    const bucket = this.table[this.hash(key)]
    const sameKeyItem = bucket?.find((item) => item[0] === key)
    return sameKeyItem ? sameKeyItem[1] : undefined
  }
 
  remove(key) {
    const bucket = this.table[this.hash(key)]
    const sameKeyItem = bucket?.find((item) => item[0] === key)
    if (sameKeyItem) return bucket.splice(bucket.indexOf(sameKeyItem), 1)
  }
}

class Graph {
  constructor() {
    this.adjacencyList = {}
  }
 
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = new Set()
  }
 
  addEdge(vertex1, vertex2) {
    this.addVertex(vertex1)
    this.addVertex(vertex2)
    this.adjacencyList[vertex1].add(vertex2)
    this.adjacencyList[vertex2].add(vertex1)
  }
 
  removeEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1]?.delete(vertex2)
    this.adjacencyList[vertex2]?.delete(vertex1)
  }
 
  removeVertex(vertex) {
    if (!this.adjacencyList[vertex]) return
    for (const adjacentVertex of this.adjacencyList[vertex]) {
      this.removeEdge(vertex, adjacentVertex)
    }
    delete this.adjacencyList[vertex]
  }
 
  hasEdge(vertex1, vertex2) {
    return !!this.adjacencyList[vertex1]?.has(vertex2) && !!this.adjacencyList[vertex2]?.has(vertex1)
  }
}

class Node {
  constructor(value) {
    this.value = value
    this.left = null
    this.right = null
  }
}
 
class BinarySearchTree {
  constructor() {
    this.root = null
  }
 
  insert(value) {
    const newNode = new Node(value)
    if (!this.root) this.root = newNode
    else this.insertNode(this.root, newNode)
  }
 
  insertNode(root, newNode) {
    if (newNode.value < root.value) {
      if (!root.left) root.left = newNode
      else this.insertNode(root.left, newNode)
    } else {
      if (!root.right) root.right = newNode
      else this.insertNode(root.right, newNode)
    }
  }
 
  search(root, value) {
    if (!root) return false
    if (root.value === value) return true
    if (value < root.value) return this.search(root.left, value)
    return this.search(root.right, value)
  }
 
  min(root) {
    return root.left ? this.min(root.left) : root.value
  }
 
  delete(value) {
    this.root = this.deleteNode(this.root, value)
  }
 
  deleteNode(root, value) {
    if (!root) return root
    if (value < root.value) root.left = this.deleteNode(root.left, value)
    else if (value > root.value) root.right = this.deleteNode(root.right, value)
    else {
      if (!root.left && !root.right) return null
      if (!root.left) return root.right
      if (!root.right) return root.left
      root.value = this.min(root.right)
      root.right = this.deleteNode(root.right, root.value)
    }
    return root
  }
 
  levelOrder() {
    const queue = [this.root]
    while (queue.length) {
      const curr = queue.shift()
      console.log(curr.value)
      if (curr.left) queue.push(curr.left)
      if (curr.right) queue.push(curr.right)
    }
  }
}

insert(10)          insert(5)           insert(15)          insert(3)
 
    10                  10                  10                  10
                       /                   /  \                /  \
                      5                   5    15             5    15
                                                             /
                                                            3