/**
* Binary search tree.
*
* @example const BST = require('dstructures').BinarySearchTree;
* const myBST = new BST();
* @description In computer science, binary search trees (BST), sometimes called
* ordered or sorted binary trees, are a particular type of container: data
* structures that store "items" (such as numbers, names etc.) in memory.
* Full wikipedia article at:
* {@link https://en.wikipedia.org/wiki/Binary_search_tree}
* @public
* @constructor
*/
class BinarySearchTree {
constructor(){
let root = null;
this.setRoot = (value) => root = value;
this.getRoot = () => root;
}
/**
* Inserts new node in a BinarySearchTree.
*
* @param {any} data Given data.
* @example BST.insert(10);
* @memberOf BinarySearchTree
*/
insert (data) {
let newNode = new _Node(data, null, null);
if (this.getRoot() === null) {
this.setRoot(newNode);
} else {
let currentNode = this.getRoot();
let parentNode;
while (true) {
parentNode = currentNode;
newNode.parent = parentNode;
if (data < currentNode.data) {
currentNode = currentNode.left;
if (currentNode === null) {
parentNode.left = newNode;
break;
}
} else {
currentNode = currentNode.right;
if (currentNode === null) {
parentNode.right = newNode;
break;
}
}
}
}
}
/**
* Returns sorted array representation of the BinarySearchTree.
*
* @returns {Array} Returns array representation of the BinarySearchTree.
* @example BST.insert(10);
* BST.insert(32);
* BST.insert(41);
* BST.inOrder(41); // [10, 32, 41]
*/
inOrder () {
let arr = [];
(function Order(node) {
if (!(node === null)) {
Order(node.left);
arr.push(node.return());
Order(node.right);
}
})(this.getRoot());
return arr;
}
/**
* Returns the smallest value within the BinarySearchTree.
*
* @returns {Any} Returns the smallest value within the BinarySearchTree.
* @example BST.insert(10);
* BST.insert(32);
* BST.insert(41);
* BST.min(); // 10
*/
min () {
const result = (function minNode(currentNode) {
if(currentNode.left === null) {
return currentNode.data
}
return minNode(currentNode.left);
})(this.getRoot());
return result;
}
/**
* Returns the biggest value within the BinarySearchTree.
*
* @returns {Any} Returns the biggest value within the BinarySearchTree.
* @example BST.insert(10);
* BST.insert(32);
* BST.insert(41);
* BST.max(); // 41
*
*/
max () {
const result = (function minNode(currentNode) {
if(currentNode.right === null) {
return currentNode.data
}
return minNode(currentNode.right);
})(this.getRoot());
return result;
}
/**
* Finds given value within the BinarySearchTree.
*
* @param {any} data Given data.
* @returns {Boolean|Any} Returns given value or false if the value is not present.
* @example BST.insert(10);
* BST.insert(32);
* BST.insert(41);
* BST.find(32); // 32
* BST.find(72); // false
*
*/
find (data) {
let currentNode = this.getRoot();
while (currentNode.data !== data) {
if (data < currentNode.data) {
currentNode = currentNode.left;
} else {
currentNode = currentNode.right;
}
if (currentNode === null) return false;
}
return currentNode.data;
}
/**
* Removes node from the BinarySearchTree.
*
* @param {any} data Given data.
* @returns {Boolean|undefined} Returns false if 'data' argument is ommited,
* or undefined if the 'data' argument value is not present within a BinarySearchTree.
* @example BST.insert(10);
* BST.insert(32);
* BST.insert(41);
* BST.remove(41); // 10, 32
*/
remove (data) {
if (!data) {
return false;
}
this.setRoot(_removeNode(this.getRoot(), data));
}
}
// =======private section===========
// Node function constructor
// @private
function _Node (data, left, right) {
this.data = data;
this.left = left;
this.right = right;
this.return = () => this.data;
this.setData = (data) => this.data = data;
}
// This is the actual removal function.
// @private
const _removeNode = function (node , data) {
if (node === null) return null;
if (node.data === data) {
// node has no children
if (node.left === null && node.right === null) return null;
// node has no left child
if (node.left === null) return node.right;
// node has no right child
if (node.right === null) return node.left;
// node has two children
var tempNode = smallestNode(node.right);
node.data = tempNode.data;
node.right = _removeNode(node.right, node.data);
return node;
} else if (data < node.data) {
node.left = _removeNode(node.left, data);
return node;
} else {
node.right = _removeNode(node.right, data);
return node;
}
}
// small helper function for removing.
// @private
const smallestNode = function (currentNode) {
const result = (function minNode(currentNode) {
if(currentNode.left === null) {
return currentNode
}
return minNode(currentNode.left);
})(currentNode);
return result;
}
module.exports = BinarySearchTree;