A binary search tree is a data structure consisting of a set of orderd linked nodes that represent a hierarchical tree structure. Each node is linked to others via parent-children relationship. Any given node can have at most two children (left and right). The first node in the binary search tree is the root, whereas nodes without any children are the leaves. The binary search tree is organized in such a way that for any given node, all nodes in its left subtree have a key less than itself and all nodes in its right subtree have a key greater than itself.
Each node in a binary search tree data structure must have the following properties:
key
: The key of the nodevalue
: The value of the nodeparent
: The parent of the node (null
if there is none)left
: A pointer to the node's left child (null
if there is none)right
: A pointer to the node's right child (null
if there is none)The main operations of a binary search tree data structure are:
insert
: Inserts a node as a child of the given parent noderemove
: Removes a node and its children from the binary search treehas
: Checks if a given node existsfind
: Retrieves a given nodepreOrderTraversal
: Traverses the binary search tree by recursively traversing each node followed by its childrenpostOrderTraversal
: Traverses the binary search tree by recursively traversing each node's children followed by the nodeinOrderTraversal
: Traverses the binary search tree by recursively traversing each node's left child, followed by the node, followed by its right childclass BinarySearchTreeNode {
constructor(key, value = key, parent = null) {
this.key = key;
this.value = value;
this.parent = parent;
this.left = null;
this.right = null;
}
get isLeaf() {
return this.left === null && this.right === null;
}
get hasChildren() {
return !this.isLeaf;
}
}
class BinarySearchTree {
constructor(key, value = key) {
this.root = new BinarySearchTreeNode(key, value);
}
*inOrderTraversal(node = this.root) {
if (node.left) yield* this.inOrderTraversal(node.left);
yield node;
if (node.right) yield* this.inOrderTraversal(node.right);
}
*postOrderTraversal(node = this.root) {
if (node.left) yield* this.postOrderTraversal(node.left);
if (node.right) yield* this.postOrderTraversal(node.right);
yield node;
}
*preOrderTraversal(node = this.root) {
yield node;
if (node.left) yield* this.preOrderTraversal(node.left);
if (node.right) yield* this.preOrderTraversal(node.right);
}
insert(key, value = key) {
let node = this.root;
while (true) {
if (node.key === key) return false;
if (node.key > key) {
if (node.left !== null) node = node.left;
else {
node.left = new BinarySearchTreeNode(key, value, node);
return true;
}
} else if (node.key < key) {
if (node.right !== null) node = node.right;
else {
node.right = new BinarySearchTreeNode(key, value, node);
return true;
}
}
}
}
has(key) {
for (let node of this.postOrderTraversal()) {
if (node.key === key) return true;
}
return false;
}
find(key) {
for (let node of this.postOrderTraversal()) {
if (node.key === key) return node;
}
return undefined;
}
remove(key) {
const node = this.find(key);
if (!node) return false;
const isRoot = node.parent === null;
const isLeftChild = !isRoot ? node.parent.left === node : false;
const hasBothChildren = node.left !== null && node.right !== null;
if (node.isLeaf) {
if (!isRoot) {
if (isLeftChild) node.parent.left = null;
else node.parent.right = null;
} else {
this.root = null;
}
return true;
} else if (!hasBothChildren) {
const child = node.left !== null ? node.left : node.right;
if (!isRoot) {
if (isLeftChild) node.parent.left = child;
else node.parent.right = child;
} else {
this.root = child;
}
child.parent = node.parent;
return true;
} else {
const rightmostLeft = [...this.inOrderTraversal(node.left)].slice(-1)[0];
rightmostLeft.parent = node.parent;
if (!isRoot) {
if (isLeftChild) node.parent.left = rightmostLeft;
else node.parent.right = rightmostLeft;
} else {
this.root = rightmostLeft;
}
rightmostLeft.right = node.right;
node.right.parent = rightmostLeft;
return true;
}
}
}
class
for the BinarySearchTreeNode
with a constructor
that initializes the appropriate key
, value
, parent
, left
and right
properties.isLeaf
getter, that uses Array.prototype.length
to check if both left
and right
are empty.hasChildren
getter, that is the reverse of the isLeaf
getter.class
for the BinarySearchTree
with a constructor
that initializes the root
of the binary search tree.preOrderTraversal()
generator method that traverses the binary search tree in pre-order, using the yield*
syntax to recursively delegate traversal to itself.postOrderTraversal()
generator method that traverses the binary search tree in post-order, using the yield*
syntax to recursively delegate traversal to itself.inOrderTraversal()
generator method that traverses the binary search tree in in-order, using the yield*
syntax to recursively delegate traversal to itself.insert()
method, that uses a while
loop to search the binary search tree, moving through each node's children, until an appropriate position is found to insert a new child BinarySearchTreeNode
either as the left
or right
child, depending on the given key
.has()
method, that uses the preOrderTraversal()
method to check if the given node exists in the binary search tree.find()
method, that uses the preOrderTraversal()
method to retrieve the given node in the binary search tree.remove()
method, that removes the given BinarySearchTreeNode
from the binary search tree, deleting any links to it and updating the binary search tree to retain its order.const tree = new BinarySearchTree(30);
tree.insert(10);
tree.insert(15);
tree.insert(12);
tree.insert(40);
tree.insert(35);
tree.insert(50);
[...tree.preOrderTraversal()].map(x => x.value);
// [30, 10, 15, 12, 40, 35, 50]
[...tree.inOrderTraversal()].map(x => x.value);
// [10, 12, 15, 30, 35, 40, 50]
[...tree.postOrderTraversal()].map(x => x.value);
// [12, 15, 10, 35, 50, 40, 30]
tree.root.value; // 30
tree.root.hasChildren; // true
tree.find(12).isLeaf; // true
tree.find(40).isLeaf; // false
tree.find(50).parent.value; // 40
tree.find(15).left.value; // 12
tree.find(12).right; // null
tree.remove(12);
[...tree.preOrderTraversal()].map(x => x.value);
// [30, 10, 15, 40, 35, 50]
tree.remove(10);
[...tree.preOrderTraversal()].map(v => ({
key: v.key,
parent: v.parent ? v.parent.key : null,
})); // [30, 15, 40, 35, 50]
tree.remove(40);
[...tree.preOrderTraversal()].map(x => x.value);
// [30, 15, 40, 35, 50]
tree.remove(30);
[...tree.preOrderTraversal()].map(x => x.value);
// [15, 35, 50]
Would you like to help us improve 30 seconds of code?Take a quick survey
Snippet collection
A guide to some of the most commonly-used data structures, along with JavaScript implementations and examples.
JavaScript, Object
A binary tree is a data structure consisting of a set of linked nodes representing a hierarchical tree structure, in which each node can have at most two children.
JavaScript, Object
A tree is a data structure consisting of a set of linked nodes representing a hierarchical tree structure.
JavaScript, Object
A doubly linked list is a linear data structure where each element points both to the next and the previous one.