<commit_before>/**
 * This creates a node
 * @name BSTNode
 * @param key
 * @param left
 * @param right
 * @return BSTNode
 */
export class BSTNode {
  constructor(key, details = null, left = null, right = null) {
    // the constructor creates the leaf node
    this._key = key;
    this._details = details;
    this._left = left;
    this._right = right;
  }

  /* Getter and Setter for key */
  get key() { return this._key; }
  set key(key) { this._key = key; }

  /* Getter and Setter for key */
  get details() { return this._details; }
  set details(details) { this._details = details; }

  /* Getter and Setter for left sub tree */
  get left() { return this._left; }
  set left(left) { this._left = left; }

  /* Getter and Setter for right sub tree */
  get right() { return this._right; }
  set right(right) { this._right = right; }
}

/**
 * Private methods name
 */
const inOrderTraversal = Symbol('inorder');
const preOrderTraversal = Symbol('preorder');
const postOrderTraversal = Symbol('postorder');

/**
 * Private properties name
 */
const length = Symbol('length');

/**
 * Binary Search Tree
 */
export class BST {
  constructor() {
    this.root = null;
    this[length] = 0;
  }

  get len() {
    return this[length];
  }

  /**
   * Insert value in the BST
   * @param {*} val
   */
  insert(val, details = null) {
    // create a BST node
    const bstNode = new BSTNode(val, details);

    /**
     * @name recurseBST
     * @param {*} node - optional, default value is this.root
     */
    const recurseBST = (node = this.root) => {
      if (node.key > val && !node.left) {
        node.left = bstNode;
        this[length]++;
      } else if (node.key > val) {
        recurseBST(node.left);
      } else if (node.key < val && !node.right) {
        node.right = bstNode;
        this[length]++;
      } else if (node.key < val) {
        recurseBST(node.right);
      }
    }

    if (!this.root) {
      // if the root is null then assign the created node to the root.
      this.root = bstNode;
      this[length]++;
    } else {
      recurseBST();
    }
  }

  delete(val) {
    if (!this.root) {
      return new Error('BST is empty. Cannot delete from empty BST');
    } else {
      let findNode = this.lookup(val);
      if (findNode.hasVal) {
        // case 1
        // when the node has no children or when its a leaf
        // then simply delete the node
        if (!findNode.currentNode.left && !findNode.currentNode.right) {
          const direction = findNode.parentNode.key > val ? 'left' : 'right';
          findNode.parentNode[direction] = null;
          this[length]--;
        }
        // case 2
        // when node has just 1 child
        // Simply delete the key and point the parent to the child
        else if (!!findNode.currentNode.left ^ !!findNode.currentNode.right) {
          const parentToCurNodeDir = findNode.parentNode.key > val ? 'left' : 'right';
          const curNodeToChildDir = findNode.currentNode.left ? 'left' : 'right';
          findNode.parentNode[parentToCurNodeDir] = findNode.currentNode[curNodeToChildDir];
          this[length]--;
        }
        // case 3
        // when node has both left and right children
        // Find minimum value in the right subtree of the node containing the key to be deleted.
        // Replace the key to be deleted with the min value.
        // Then delete the min val from the right subtree.
        else if (findNode.currentNode.left && findNode.currentNode.right) {
          // find successor
          const successor = this.findMin(findNode.currentNode.right);
          findNode.currentNode.key = successor.subtree.key;
          successor.parent.left = null;
          this[length]--;
        }
      } else {
        return new Error('Node not found.');
      }
    }
  }

  /**
   * Find minimum node of the given subtree. If subtree is not passed then
   * @param {BST} subtree
   * @returns {BST, BST} returns min node and its parent
   */
  findMin(subtree = this.root) {
    let parent;
    while (subtree.left) {
      parent = subtree;
      subtree = subtree.left;
    }
    return { subtree, parent };
  }

  /**
   * Looks for a value in the BST.
   * @param {string|number} val
   * @return {object} response
   */
  lookup(val) {
    let response = { hasVal: false, currentNode: null, parentNode: null };
    const lookRecursively = (node = this.root, parent = null) => {
      if (node.key === val) {
        response.hasVal = true;
        response.currentNode = node;
        response.parentNode = parent;
      } else if (node.left && node.key > val) {
        lookRecursively(node.left, node);
      } else if (node.right && node.key < val) {
        lookRecursively(node.right, node);
      }
    }

    lookRecursively();
    return response;
  }

  /**
   * Print the values of the BST in specific order
   * @param {string} type - value of type can be inOrder, preOrder, postOrder<commit_msg>Added check for deletion of only root noot having no children Added check for lookup of empty BST<commit_after>/**
 * This creates a node
 * @name BSTNode
 * @param key
 * @param left
 * @param right
 * @return BSTNode
 */
export class BSTNode {
  constructor(key, details = null, left = null, right = null) {
    // the constructor creates the leaf node
    this._key = key;
    this._details = details;
    this._left = left;
    this._right = right;
  }

  /* Getter and Setter for key */
  get key() { return this._key; }
  set key(key) { this._key = key; }

  /* Getter and Setter for key */
  get details() { return this._details; }
  set details(details) { this._details = details; }

  /* Getter and Setter for left sub tree */
  get left() { return this._left; }
  set left(left) { this._left = left; }

  /* Getter and Setter for right sub tree */
  get right() { return this._right; }
  set right(right) { this._right = right; }
}

/**
 * Private methods name
 */
const inOrderTraversal = Symbol('inorder');
const preOrderTraversal = Symbol('preorder');
const postOrderTraversal = Symbol('postorder');

/**
 * Private properties name
 */
const length = Symbol('length');

/**
 * Binary Search Tree
 */
export class BST {
  constructor() {
    this.root = null;
    this[length] = 0;
  }

  get len() {
    return this[length];
  }

  /**
   * Insert value in the BST
   * @param {*} val
   */
  insert(val, details = null) {
    // create a BST node
    const bstNode = new BSTNode(val, details);

    /**
     * @name recurseBST
     * @param {*} node - optional, default value is this.root
     */
    const recurseBST = (node = this.root) => {
      if (node.key > val && !node.left) {
        node.left = bstNode;
        this[length]++;
      } else if (node.key > val) {
        recurseBST(node.left);
      } else if (node.key < val && !node.right) {
        node.right = bstNode;
        this[length]++;
      } else if (node.key < val) {
        recurseBST(node.right);
      }
    }

    if (!this.root) {
      // if the root is null then assign the created node to the root.
      this.root = bstNode;
      this[length]++;
    } else {
      recurseBST();
    }
  }

  delete(val) {
    if (!this.root) {
      return new Error('BST is empty. Cannot delete from empty BST');
    } else {
      let findNode = this.lookup(val);
      if (findNode.hasVal) {
        // case 1
        // when the node has no children or when its a leaf
        // then simply delete the node
        if (!findNode.currentNode.left && !findNode.currentNode.right) {
          //check if the node is the root node
          if (findNode.parentNode === null) {
            this.root = null;
          } else {
            const direction = findNode.parentNode.key > val ? 'left' : 'right';
            findNode.parentNode[direction] = null;
          }
          this[length]--;
        }
        // case 2
        // when node has just 1 child
        // Simply delete the key and point the parent to the child
        else if (!!findNode.currentNode.left ^ !!findNode.currentNode.right) {
          const parentToCurNodeDir = findNode.parentNode.key > val ? 'left' : 'right';
          const curNodeToChildDir = findNode.currentNode.left ? 'left' : 'right';
          findNode.parentNode[parentToCurNodeDir] = findNode.currentNode[curNodeToChildDir];
          this[length]--;
        }
        // case 3
        // when node has both left and right children
        // Find minimum value in the right subtree of the node containing the key to be deleted.
        // Replace the key to be deleted with the min value.
        // Then delete the min val from the right subtree.
        else if (findNode.currentNode.left && findNode.currentNode.right) {
          // find successor
          const successor = this.findMin(findNode.currentNode.right);
          findNode.currentNode.key = successor.subtree.key;
          successor.parent.left = null;
          this[length]--;
        }
      } else {
        return new Error('Node not found.');
      }
    }
  }

  /**
   * Find minimum node of the given subtree. If subtree is not passed then
   * @param {BST} subtree
   * @returns {BST, BST} returns min node and its parent
   */
  findMin(subtree = this.root) {
    let parent;
    while (subtree.left) {
      parent = subtree;
      subtree = subtree.left;
    }
    return { subtree, parent };
  }

  /**
   * Looks for a value in the BST.
   * @param {string|number} val
   * @return {object} response
   */
  lookup(val) {
    let response = { hasVal: false, currentNode: null, parentNode: null };
    const lookRecursively = (node = this.root, parent = null) => {
      if (node) {
        if (node.key === val) {
          response.hasVal = true;
          response.currentNode = node;
          response.parentNode = parent;
        } else if (node.left && node.key > val) {
          lookRecursively(node.left, node);
        } else if (node.right && node.key < val) {
          lookRecursively(node.right, node);
        }
      }
    }

    lookRecursively();
    return response;
  }

  /**
   * Print the values of the BST in specific order
   * @param {string} type - value of type can be inOrder, preOrder, postOrder
{'fraction_non_alphanumeric': 0.12191055315810122, 'fraction_numerical': 0.000980776775205963, 'mean_word_length': 2.164804469273743, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6604076', 'n_tokens_mistral': 3137, 'n_tokens_neox': 3099, 'n_words': 970}