bstClass.js

/*
@file

@legend
n = node

@tasks
minnode method is missing
*/


/**
@func util

@param {*} v value to stringify then log
*/
export const logDeepStringify = v => console.log(JSON.stringify(v, undefined, "  "));


/*
@class
*/
class Node {
  constructor(data) {
    this.data = data; // node value
    this.left = null;   // left node child reference
    this.right = null; // right node child reference
  }
}




/*
@class
*/
class BinarySearchTree {
  constructor() {
    this.root = null; // root of bst
  }



  insert(data) {
    let newNode = new Node(data);

    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode); // helper method below
    }
  }

  /**
  @method recursive
  */
  insertNode(n, newNode) {
    if (newNode.data < n.data) {
      if (n.left === null) {
        n.left = newNode;
      } else {
        this.insertNode(n.left, newNode);
      }
    } else {
      if (n.right === null) {
        n.right = newNode;
      } else {
        this.insertNode(n.right, newNode);
      }
    }
  }



  /**
  @method recursive
  */
  inOrderTraverse(n, callback) {
    if (n != null) {
      this.inOrderTraverse(n.left, callback);
      callback(n.data);
      this.inOrderTraverse(n.right, callback);
    }
  }



  /**
  @method recursive
  */
  preOrderTraverse(n, callback) {
    if (n != null) {
      callback(n.data);
      this.preOrderTraverse(n.left, callback);
      this.preOrderTraverse(n.right, callback);
    }
  }



  /**
  @method recursive
  */
  postOrderTraverse(n, callback) {
    if (n != null) {
      this.postOrderTraverse(n.left, callback);
      this.postOrderTraverse(n.right, callback);
      callback(n.data);
    }
  }



  /**
  @method recursive
  */
  search(n, data) {
    if (n === null) {
      return null;
    } else if (data < n.data) {
      return this.search(n.left, data);
    } else if (data > n.data) {
      return this.search(n.right, data);
    } else {
      return n;
    }
  }



  remove(data) {
    this.root = this.removeNode(this.root, data); // helper method below
  }

    
  /**
  @method recursive
  */
  removeNode(n, data) {
    if (n === null) {
      return null;
      // if data to be deleted is less than the root's data, move to the left subtree
    } else if (data < n.data) {
      n.left = this.removeNode(n.left, data);
      return n;
      // if data to be deleted is greater than the root's data, move to the right subtree
    } else if (data > n.data) {
      n.right = this.removeNode(n.right, data);
      return n;
      // if data is similar to the root's data, delete the node
    } else {
      // delete node with no children (leaf node)
      if (n.left === null && n.right === null) {
        n = null;
        return n;
      }

      // delete node with one child
      if (n.left === null) {
        n = n.right;
        return n;
      } else if (n.right === null) {
        n = n.left;
        return n;
      }

      // delete node with two children
      // minimum node of the right subtree is stored in newNode
      let newNode = this.minNode(n.right);
      n.data = newNode.data;
      n.right = this.removeNode(n.right, newNode.data);
      return n;
    }
  }

} //end class

//@tests
const bst = new BinarySearchTree();
const ar = [11, 7, 9, 15, 6]
ar.forEach(n => bst.insert(n));
logDeepStringify(bst);
/*
produces...
     11
   7   15
 6 9

output:
{
  "root": {
    "data": 11,
    "left": {
      "data": 7,
      "left": {
        "data": 6,
        "left": null,
        "right": null
      },
      "right": {
        "data": 9,
        "left": null,
        "right": null
      }
    },
    "right": {
      "data": 15,
      "left": null,
      "right": null
    }
  }
}
*/