In-class live coding result of the binary search tree homework - read, learn, please don't copy/paste without brain activity pls

bst.ts

// bst.ts

// ---------------------------------------------------------    [ Types ]

/**
 * A binary search tree structure simply contains the root node of a binary
 * search tree. If the tree is empty, the root node is null.
 *
 * This structure is simply used to contain the root node of the tree. During
 * mutation operations it is possible for the root node to change.
 */
export type BinarySearchTree = {
  root: BTNode | null;
};

/**
 * A binary search tree node contains a piece of data, and references to the
 * left and right children. If there is no left or right child, the
 * corresponding reference is null.
 *
 * The data found on the left side of the tree is strictly less than the data in
 * this node. The data on the right side should be greater than or equal to this
 * data. Duplicate values in the tree are allowed, however each individual node
 * is independent.
 */
export type BTNode = {
  data: number;
  left: BTNode | null;
  right: BTNode | null;
};

// ---------------------------------------------------------    [ Initialize ]

/**
 * Initialize a new, empty BinarySearchTree instance and return it.
 */
export const initTree = (): BinarySearchTree => {
  return {
    root: null,
  };
};

/**
 * Initialize a new BTNode instance with the given data and no child data, and
 * return it.
 */
export const initNode = (data: number): BTNode => {
  return {
    data: data,
    left: null,
    right: null,
  };
};

// ---------------------------------------------------------    [ Operations ]

/**
 * Inserts a new BTNode with the given data into the tree. This new node should
 * be placed in the correct location according to the invariants described in
 * the BTNode type. If this operation establishes a different tree root, the
 * `tree` argument's `root` field should be updated accordingly.
 */
export const insert = (tree: BinarySearchTree, data: number): void => {
  if (tree.root == null) {
    tree.root = initNode(data);
    return;
  }
  // we know that tree.root is not null here.
  insertRecursively(tree.root, data);
};

const insertRecursively = (node: BTNode, data: number): void => {
  // check to see if the data value is greater or less than node.data. If it is
  // greater or equal, go to the right, otherwise go left.
  if (data < node.data) {
    // go left
    if (node.left == null) {
      // there's room right here
      node.left = initNode(data);
      return;
    } else {
      // taken - need to recurse
      insertRecursively(node.left, data);
    }
  } else {
    // go right
    if (node.right == null) {
      node.right = initNode(data);
      return;
    } else {
      insertRecursively(node.right, data);
    }
  }
};

/**
 * Searches the tree for a node with the given data. Returns true if such a node
 * is found, false otherwise.
 */
export const contains = (root: BTNode, data: number): boolean => {
  return getNode(root, data) != null; // Laziness! We can reuse code now
};

/**
 * Searches the tree for a node with the given data. Returns the node if found,
 * null otherwise.
 */
export const getNode = (root: BTNode, data: number): BTNode => {
  if (root == null) {
    return null;
  }
  if (root.data == data) {
    return root;
  }
  if (data < root.data) {
    // left
    return getNode(root.left, data);
  } else {
    // right
    return getNode(root.right, data);
  }
};

/**
 * Returns the number of non-null nodes accessible from the given root node.
 */
export const size = (root: BTNode): number => {
  // IMPLEMENT
  return NaN;
};

/**
 * Returns a Javascript list containing the data in the tree in non-decreasing
 * order. If the given tree is empty, the returned list is empty.
 */
export const toArray = (root: BTNode): number[] => {
  // IMPLEMENT
  return null;
};

/**
 * Removes a BTNode with the given data from the tree, if such a node exists. If
 * no such tree exists, do nothing. If this operation establishes a different
 * tree root, the `tree` argument's `root` field should be updated accordingly.
 */
export const remove = (tree: BinarySearchTree, data: number): void => {
  // IMPLEMENT
  return;
};