Binary Search Tree

Insert

We start searching for a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.

insert

export class BinaryNode {
  left: BinaryNode | null = null
  right: BinaryNode | null = null

  constructor(public data: number) {}

  insert(data: number): boolean {
    if (data === this.data) {
      return false
    }

    const isGoLeft = data < this.data
    const next = isGoLeft ? this.left : this.right

    if (next === null) {
      const newNode = new BinaryNode(data)
      if (isGoLeft) {
        this.left = newNode
      } else {
        this.right = newNode
      }

      return true
    }

    return next.insert(data)
  }
}

Delete

We start searching for the node from root. If found, we have 3 possibilities:

1. Node to be deleted is the leaf: Simply remove it from the tree.

2. Node to be deleted has only one child: move the child up to replace the node.

3. Node to be deleted has two children: Find the inorder successor of the node. Replace the node with the inorder successor and delete the inorder successor (case 1 or 2).

tip

In-order successor can be obtained by finding the minimum value in the right child of the node.

Inorder predecessor can also be used.

delete

export class BinaryNode {
  left: BinaryNode | null = null
  right: BinaryNode | null = null

  constructor(public data: number) {}

  delete(data: number): BinaryNode | null {
    if (data < this.data) {
      if (this.left) this.left = this.left.delete(data)
    } else if (data > this.data) {
      if (this.right) this.right = this.right.delete(data)
    } else {
      // Found the node at leaf or has only 1 child
      if (this.left === null) {
        return this.right
      }

      if (this.right === null) {
        return this.left
      }

      // Found the node that has 2 children
      // replace with in-order successor (min value of right subtree)
      const nextVal = this.right.minValue()
      this.data = nextVal

      // delete the in-order successor
      this.right = this.right.delete(nextVal)
    }

    return this
  }

  minValue(): number {
    let node = this as BinaryNode
    while (node.left) node = node.left

    return node.data
  }
}

Source

export class BinaryNode {
  left: BinaryNode | null = null
  right: BinaryNode | null = null

  constructor(public data: number) {}

  search(data: number): BinaryNode | null {
    if (data === this.data) {
      return this
    }

    const next = data < this.data ? this.left : this.right

    return next === null ? null : next.search(data)
  }

  insert(data: number): boolean {
    if (data === this.data) {
      return false
    }

    const isGoLeft = data < this.data
    const next = isGoLeft ? this.left : this.right

    if (next === null) {
      const newNode = new BinaryNode(data)
      if (isGoLeft) {
        this.left = newNode
      } else {
        this.right = newNode
      }

      return true
    }

    return next.insert(data)
  }

  delete(data: number): BinaryNode | null {
    if (data < this.data) {
      if (this.left) this.left = this.left.delete(data)
    } else if (data > this.data) {
      if (this.right) this.right = this.right.delete(data)
    } else {
      if (this.left === null) {
        return this.right
      }

      if (this.right === null) {
        return this.left
      }

      // replace with min value of right subtree
      const nextVal = this.right.minValue()
      this.data = nextVal

      // delete min value of right subtree
      this.right = this.right.delete(nextVal)
    }

    return this
  }

  traverseInOrder(cb: (data: number) => void): void {
    if (this.left) {
      this.left.traverseInOrder(cb)
    }

    cb(this.data)

    if (this.right) {
      this.right.traverseInOrder(cb)
    }
  }

  traversePreOrder(cb: (data: number) => void): void {
    cb(this.data)

    if (this.left) {
      this.left.traversePreOrder(cb)
    }

    if (this.right) {
      this.right.traversePreOrder(cb)
    }
  }

  traversePostOrder(cb: (data: number) => void): void {
    if (this.left) {
      this.left.traversePostOrder(cb)
    }

    if (this.right) {
      this.right.traversePostOrder(cb)
    }

    cb(this.data)
  }

  minValue(): number {
    let node = this as BinaryNode
    while (node.left) node = node.left

    return node.data
  }
}

export class BinaryTree {
  root: BinaryNode | null = null

  search(data: number): BinaryNode | null {
    return this.root ? this.root.search(data): null
  }

  insert(data: number): boolean {
    if (!this.root) {
      this.root = new BinaryNode(data)
      return true
    }

    return this.root.insert(data)
  }

  delete(data: number): void {
    if (!this.root) {
      return
    }

    this.root = this.root.delete(data)
  }
}