Construct Binary Search Tree

bfs.ts

function bfs<T>(tree: BSTNode<T>, fn: (n: T) => void) {
  const queue = [tree];
  
  while (queue.length) {
    const cur = queue.shift();
  
    if (cur.left) queue.push(cur.left);
    if (cur.right) queue.push(cur.right);
  
    fn(cur.value);
  }
}
  
a = [4, 5, 10, 2, 3, 1];
b = toBST(a);
  
list = [];
bfs(b, n => list.push(n)); /** [4, 2, 5, 1, 3, 10] */

binary-search.ts

/**
 * Binary search algorithm takes O(log n) time to find a node that matches `value` within a tree.
 */

interface BSTNode<T> {
  left: null | BSTNode<T>;
  right: null | BSTNode<T>;
  value: T;
}
function binarySearch<T>(tree: BSTNode<T>, value: T) {
    let cur = tree;

    while (cur && cur.value !== value) {
        const dir = value > cur.value ? 'right' : 'left';
        const subtree = cur[dir];

        // If `subtree` is `null`, return `cur` which is its parent node.
        if (null == subtree) break;
      
        cur = subtree;
    }

    return cur;
}

bst-contains.ts

/**
 * Since `binarySearch(tree, value)` takes `O(log n)` time to search a node that matches `value`,
 * the time complexity of this function is hence also `O(log n)` as `node.value === value` takes
 * constant time to execute.
 */

function bstContains<T>(tree: BSTNode<T>, value: T) {
    const node = binarySearch<T>(tree, value);

    return node.value === value;
}
  
a = [4, 5, 10, 2, 3, 1];
b = toBST(a);
  
bstContains(a, 10) === true;
bstContains(a, 12) === false;

bst-insert.ts

/**
 * Time complexity's breakdown:
 *  - `binarySearch(tree, value)` - O(log n)
 *  - `const dir = ...` - O(1)
 *  - `node[dir] = ...` - O(1)
 *
 *  Constant time execution can be omitted for a worst-case scenario: O(log n) for insertion.
 */

function bstInsert<T>(tree: BSTNode<T>, value: T) {
    const node = binarySearch<T>(tree, value);
    const dir = value > node.value ? 'right' : 'left';

    node[dir] = toNode(value);
}

a = [4, 5, 10, 2, 3, 1];
b = toBST(a);

bstContains(b, 33) === false;
bstInsert(b, 33);
bstContains(b, 33) === true;

bst-remove.ts

// Time complexity: O(h) or O(log n)
// Space complexity: O(h) or O(log n)
function findMinRightNode<T>(tree: BSTNode<T>): null | BSTNode<T> {
  // Find the smallest node on the right subtree.
  let c = tree.right;
  while (c) {
    const dir = null == c.left ? 'right' : 'left';
    const subtree = c[dir];
  
    // If the smallest leaf node is found, disconnect the node from its parent and return the node.
    if (null == subtree.left && null == subtree.right) {
      c[dir] = null;
      return subtree;
    }
  
    c = subtree;
  }
  
  tree.right = null;
  return c;
}

// Time complexity: O(h) or O(log n)
// Space complexity: O(h) or O(log n) due to the recursive stack space even though `findMinRightNode` is also O(h) space.
//                   This is due to the entire space used is still logarithmic as `findMinRightNode` starts from the next
//                   level which can be seen as another `bstRemove` basically.
function bstRemove<T>(tree: BSTNode<T>, value: T): null | BSTNode<T> {
  if (null == tree) return tree;
  
  if (tree.value == value) {
    if (null == tree.left && null == tree.right) return null;
    if (null == tree.left) return tree.right;
    if (null == tree.right) return tree.left;
  
    const minNode = findMinRightNode(tree);
  
    minNode.left = tree.left;
    minNode.right = tree.right;
    tree.left = tree.right = null;
  
    return minNode;
  }
  
  const dir = value > tree.value ? 'right' : 'left';
  
  tree[dir] = bstRemove(tree[dir], value);
  
  return tree;
}

dfs.ts

function dfs<T>(tree: BSTNode<T>, fn: (n: T) => void) {
  const stack = [tree];
  
  while (stack.length) {
    const cur = stack.pop();
  
    if (cur.right) stack.push(cur.right);
    if (cur.left) stack.push(cur.left);
  
    fn(cur.value); // pre-order DFS traversal
  }
}
  
a = [4, 5, 10, 2, 3, 1];
toBST(a);
  
list = [];
dfs(a, n => list.push(n)); /** [4, 2, 1, 3, 5, 10] */
 
// Reference: https://medium.com/quick-code/data-structures-traversing-trees-9473f6d9f4ef
function dfsRecursive<T>(tree: BSTNode<T>, fn: (n: T) => void, order = 0) {
  if (0 === order) fn(tree.value); // pre-order
  
  if (tree.left) dfsRecursive(tree.left, fn, order);
  
  if (1 === order) fn(tree.value); // in-order
  
  if (tree.right) dfsRecursive(tree.right, fn, order);
  
  if (2 === order) fn(tree.value); // post-order
}
  
a = [4, 5, 10, 2, 3, 1];
toBST(a);
  
list = [];
dfsRecursive(a, n => list.push(n)); /** [4, 2, 1, 3, 5, 10] */
  
list = [];
dfsRecursive(a, n => list.push(n), 1); /** [1, 2, 3, 4, 10, 5] */
  
list = [];
dfsRecursive(a, n => list.push(n), 2); /** [1, 3, 2, 10, 5, 4] */

to-bst.ts

/**
 * Time complexity: O(n * log n) = O(n log n) // O(log n) search for node insertion for n node traversal
 * Space complexity: O(n) where n are the spaces for all the nodes in a tree
 */

interface BSTNode<T> {
  left: null | BSTNode<T>;
  right: null | BSTNode<T>;
  value: T;
}
function toBST<T>(list: T[]): BSTNode<T> {
  const len = list.length;
  const tree: BSTNode<T> = toNode(list[0]);

  // Traverse the list item takes O(n) time
  for (let i = 1; i < len; i += 1) {
    const val = list[i];
    let cur = tree;

    // Finding the right position to insert new node takes O(log n)
    while (cur) {
      const dir = val > cur.value ? 'right' : 'left';
      const subtree = cur[dir];

      if (!subtree) { cur[dir] = toNode(val); break; }
      cur = subtree;
    }
  }

  return tree;
}

a = [4, 5, 10, 2, 3, 1];
toBST(a);

to-node.ts

function toNode<T>(value: T): BSTNode<T> {
  return { value, left: null, right: null };
}
  
toNode(33); // { value: 33, left: null, right: null }

Binary Search Tree

Available modules

• toNode(value) - Creates a BST node with a defined value.
• toBST(list) - Creates a BST with an array of elements.
• binarySearch(tree, value) - Binary search a BST that matches value in O(log n) time.
• bstInsert(tree, value) - Binary search a BST and returns a node that can insert value.
• bstContains(tree, value) - Binary search a BST and returns true if there is a node found to match value.
• bfs(tree, fn) - Breadth-first-search a BST and returns a list of the traversed nodes.
• dfs(tree, fn) - Iteratively depth-first-search (Pre-order traversal) a BST and returns a list of traversed nodes.
• dfsRecursive(tree, fn[, order = 0]) - Recursively depth-first-search a BST with different order (Pre-order, In-order, Post, order) and returns a list of traversed nodes.