Binary Search Tree in Node

bynary-tree.js

const DIREECTION = {
	LEFT: 'LEFT',
	RIGHT: 'RIGHT',
};

class Node {
	constructor(data, parent = null) {
		this.data = data;
		this.parent = parent;
		this.level = parent ? (parent.level + 1) : 1;
	}

	isLeaf() {
		return this.left === null && this.right === null;
	}

	getDirection() {
		if (this.parent.left) {
			return DIREECTION.LEFT;
		}

		return DIREECTION.RIGHT;
	}

	insert(data) {
		if (data < this.data) {
			if (this.left) {
				return this.left.insert(data);
			}
			else{
				this.left = new Node(data, this);
				return this.left;
			}
		}
		else if (data > this.data) {
			if (this.right) {
				return this.right.insert(data);
			}
			else{
				this.right = new Node(data, this);
				return this.right;
			}
		}
	}

	find(data) {
		if (this.data === data) {
			return this;
		}

		if (data < this.data && this.left) {
			return this.left.find(data);
		}
		else if (data > this.data && this.right) {
			return this.right.find(data);
		}

		return null;
	}

	delete() {
		// First case, is a leaf
		if (this.isLeaf()) {
			// Check what kind of leaf it is
			if (this.parent.left && this.parent.left.data === data) {
				this.parent.left = null;
				delete this.parent['left'];
			}
			else if (this.parent.right.data === data) {
				this.parent.right = null;
				delete this.parent['right'];
			}
		}
		// Node to be deleted has only one child
		else if (this.left && !this.right || this.right && !this.left) {
			const child = this.left !== null ? this.left : this.right;
			const direction = this.getDirection().toLowerCase();
			this.parent[direction] = child;
		}
		// Node to be deleted has two children
		// This is the most tricky case. If node to be deleted has two children (left child and right child), then
		// Find the minimum element (successor) from the right sub-tree
		// Replace the value of the node to be deleted with the successor.
		// Remove the minimum element from the right sub-tree.
		else {
			// Get succesor
			const minNode = this.getSucessor();
			// Get direction of node to delete
			const direction = this.getDirection().toLowerCase();
			// Replace current child with succesor
			this.parent[direction] = minNode;

			// Delete succesor from old link
			minNode.parent.left = null;
			delete minNode.parent['left'];
		}
	}

	/**
	 * Get sucessor
	 */
	getSucessor() {
		return this.right ? this.right.getMinimum() : null;
	}

	/**
	 * Get minimum node
	 */
	getMinimum() {
		if (this.left) {
			return this.left.getMinimum();
		}

		return this;
	}

	/**
	 * Get InOrder traversal approach: Left - Root - Right
	 */
	inOrder(onVisit) {
		this.left && this.left.inOrder(onVisit);

		onVisit(this);

		this.right && this.right.inOrder(onVisit);
	}
}

class BinaryTree {
	constructor(data) {
		this.root = new Node(data);
		this.maxLevel = 1;
		this.deepest = null;
	}

	add(data) {
		const node = this.root.insert(data);
		if (node.level > this.maxLevel) {
			this.maxLevel = node.level;
			this.deepest = node;
		}
	}

	getNodes() {
		const list = [];
		this.root.inOrder(node => {
			list.push(node);
		});
		return list;
	}

	getExtremes() {
		const nodes = this.getNodes();
		return {min: nodes[0], max: nodes[nodes.length - 1]};
	}

	getMax() {
		return this.getNodes()[0];
	}

	get(data) {
		const node = this.root.find(data);

		if (!node) {
			throw new Error(`Note not found for ${data}`);
		}

		return node;
	}

	print() {
		this.root.inOrder(node => {
			console.log(node.data);
		});
	}
}

const tree = new BinaryTree(20);
tree.add(9);
tree.add(28);
tree.add(5);
tree.add(12);
tree.add(21);
tree.add(32);
tree.add(11);
tree.add(14);
tree.add(30);
tree.add(36);
tree.add(29);
tree.add(34);

// console.log(tree.print());
// console.log('tree levels', tree.maxLevel);
// console.log('deepest', tree.deepest);
// console.log('extremes', tree.getExtremes());
console.log('Sucessor(20) = ', tree.get(20).getSucessor().data);
console.log('Sucessor(9) = ', tree.get(9).getSucessor().data);
console.log('Sucessor(12) = ', tree.get(12).getSucessor().data);
console.log('Sucessor(28) = ', tree.get(28).getSucessor().data);
console.log('Sucessor(32) = ', tree.get(32).getSucessor().data);