Binary trees are widely used in computer science, and learning them helps us write efficient algorithms for inserting, deleting, and searching nodes. The node definition of a binary tree: A node has at most two child nodes, namely the left child and the right child.
A binary search tree is a type of binary tree where the key value of each parent node is greater than its left child and less than its right child.
Outline of Binary Search Tree Implementation
This article will use JavaScript to implement a binary search tree with the following methods:
- constructor(): Constructor to initialize a binary search tree
- insert(value): Search for a node in the binary tree; return true if it exists, otherwise false
- preOrderTraverse(cb): Pre-order traversal
- inOrderTraverse(cb): In-order traversal
- postOrderTraverse(cb): Post-order traversal
- minNodeValue(): Minimum node value
- maxNodeValue(): Maximum node value
- removeNode(value): Remove a node
- destroy(): Destroy the nodes
Note: Many methods for implementing binary search trees in this article will use a lot of recursion. If you are not familiar with it, you can look up materials to learn.
Initializing a Binary Search Tree
Declare a BST class and define its structure in the constructor():
class BST {
constructor () {
this.root = null; // Initialize the root node
this.count = 0; // Record the number of nodes in the binary search tree
/**
* Instantiate a node; you will see this in the insert method
*/
this.Node = function(value) {
return {
value, // Node value
count: 1, // Node count, allowing duplicate nodes
left: null, // Left child node
right: null, // Right child node
}
}
}
Similar to the doubly linked list introduced in the previous article on sequential lists, we use left and right to point to the left and right child nodes.
Inserting Nodes into a Binary Search Tree
Define the insert method, which takes a value for the node to be inserted. Internally, it calls the INSERT_RECURSIVE() recursive function to insert the node and returns the result to root.
/**
* Insert an element into the binary search tree
* @param { Number } value
*/
insert(value) {
this.root = this[INSERT_RECUSIVE](this.root, value);
}
INSERT_RECUSIVE is declared using Symbol
const INSERT_RECUSIVE = Symbol('BST#recursiveInsert');
The main purpose is to achieve privatization, only called internally in the class, similar to a Private declaration.
/**
* Recursive insertion
* The insertion process is similar to a linked list; it is recommended to learn linked lists first for easier understanding
* @param { Object } node
* @param { Number } value
*/
[INSERT_RECUSIVE](node, value) {
// {1} If the current node is empty, create a new node (recursion to the bottom)
if (node === null) {
this.count++; // Increment node count by 1
return new this.Node(value);
}
// {2} Node count unchanged, indicating the value to update equals a node value in the binary tree
if (value === node.value) {
node.count++; // Increment node count by 1
} else if (value < node.value) { // {3} New inserted child node is on the left of the binary tree, continue recursive insertion
node.left = this[INSERT_RECUSIVE](node.left, value);
} else if (value > node.value) { // {4} New inserted child node is on the right of the binary tree, continue recursive insertion
node.right = this[INSERT_RECUSIVE](node.right, value);
}
return node;
}
The following diagram shows a tree structure. We use the code we just wrote to test and generate a binary search tree as shown in the structure:
Initially, I need to create a new bST object instance and execute the insert method to insert nodes
- First execution bST.insert(30) The tree is empty, code line {1} will be executed, calling new this.Node(value) to insert a new node.
- Second execution bST.insert(25) The tree is not empty, 25 is smaller than 30 (value < node.value), code line {3} will be executed, recursively insert on the left side of the tree and call INSERT_RECUSIVE method passing node.left. In the second recursion, since node.left is already null, insert a new node
- Third execution bST.insert(36) Similarly, execution order is {4} -> recursion {1}
const bST = new BST();
bST.insert(30);
bST.insert(25);
bST.insert(36);
bST.insert(20);
bST.insert(28);
bST.insert(32);
bST.insert(40);
console.dir(bST, { depth: 4 })
Searching for Nodes in a Binary Search Tree
In JavaScript, we can use hasOwnProperty to check if a specified key exists in an object. Now, we implement a similar method in binary search, passing a value to determine if it exists in the binary search tree
/**
* Search for a node in the binary tree
* @param { Number } value
* @return { Boolean } [true|false]
*/
search(value) {
return this[SEARCH_RECUSIVE](this.root, value);
}
Similarly, declare a SEARCH_RECUSIVE helper function to implement recursive search
- Line {1} First check if the passed node is null, if equal to null, it means search failed, return false.
- Line {2} Indicates the node has been found, return true.
- Line {3} Indicates the node to find is smaller than the current node, search on the left side
/**
* Recursive search for a node
* @param { Object } node
* @param { Number } value
* @return { Boolean } [true|false]
*/
[SEARCH_RECUSIVE](node, value) {
// {1} If node is null, return false
if (node === null) {
return false;
}
// {2} Node found
if (value === node.value) {
return true;
} else if (value < node.value) { // {3} Search on the left
return this[SEARCH_RECUSIVE](node.left, value);
} else if (value > node.value) { // {4} Search on the right
return this[SEARCH_RECUSIVE](node.right, value);
}
}
Binary Search Tree Traversal
There are three common ways to traverse a binary search tree: pre-order traversal, in-order traversal, and post-order traversal.
Pre-Order Traversal
Pre-order traversal visits the root first, then the left subtree, then the right subtree.
/**
* Pre-order traversal
* @param { Function } cb Callback function
*/
preOrderTraverse(cb) {
this[PRE_ORDER_TRAVERSE](this.root, cb);
}
Recursive implementation of pre-order traversal
/**
* Recursive pre-order traversal
* @param { Object } node
* @param { Function } cb
*/
[PRE_ORDER_TRAVERSE](node, cb) {
if (node !== null) {
cb(node.value); // Visit root
this[PRE_ORDER_TRAVERSE](node.left, cb); // Traverse left subtree
this[PRE_ORDER_TRAVERSE](node.right, cb); // Traverse right subtree
}
}
In-Order Traversal
In-order traversal visits the left subtree first, then the root, then the right subtree. For a binary search tree, in-order traversal yields an ascending sorted sequence.
/**
* In-order traversal
* @param { Function } cb Callback function
*/
inOrderTraverse(cb) {
this[IN_ORDER_TRAVERSE](this.root, cb);
}
Recursive implementation of in-order traversal
/**
* Recursive in-order traversal
* @param { Object } node
* @param { Function } cb
*/
[IN_ORDER_TRAVERSE](node, cb) {
if (node !== null) {
this[IN_ORDER_TRAVERSE](node.left, cb); // Traverse left subtree
cb(node.value); // Visit root
this[IN_ORDER_TRAVERSE](node.right, cb); // Traverse right subtree
}
}
Post-Order Traversal
Post-order traversal visits the left subtree first, then the right subtree, then the root.
/**
* Post-order traversal
* @param { Function } cb Callback function
*/
postOrderTraverse(cb) {
this[POST_ORDER_TRAVERSE](this.root, cb);
}
Recursive implementation of post-order traversal
/**
* Recursive post-order traversal
* @param { Object } node
* @param { Function } cb
*/
[POST_ORDER_TRAVERSE](node, cb) {
if (node !== null) {
this[POST_ORDER_TRAVERSE](node.left, cb); // Traverse left subtree
this[POST_ORDER_TRAVERSE](node.right, cb); // Traverse right subtree
cb(node.value); // Visit root
}
}
Destroying the Binary Search Tree
To destroy the binary search tree, we can use post-order traversal to recursively delete nodes.
/**
* Destroy the binary search tree using post-order traversal
*/
destroy(){
this.root = this[DESTORY_RECUSIVE](this.root);
}
Define a DESTORY_RECUSIVE method for recursive calls, which is essentially a post-order traversal.
/**
* Destroy binary search tree recursive call
* @param { Object } node
*/
[DESTORY_RECUSIVE](node) {
if (node !== null) {
this[DESTORY_RECUSIVE](node.left);
this[DESTORY_RECUSIVE](node.right);
node = null;
this.count--;
return node;
}
}
Maximum and Minimum Nodes
Recall the definition of a binary search tree: “A parent node is greater than its left child and less than its right child.” Based on this rule, we can easily find the minimum and maximum values.
Finding the Minimum Node Value in the Binary Tree
To find the minimum value, search to the left of the binary tree until the node’s left is null, indicating it is the minimum.
/**
* Find the minimum node value in the binary tree
* @return value
*/
minNodeValue() {
const result = this.minNode(this.root);
return result !== null ? result.value : null;
}
Finding the minimum node
/**
* Find the minimum node
*/
minNode(node) {
if (node === null) {
return node;
}
while (node && node.left !== null) {
node = node.left;
}
return node;
}
Finding the Maximum Node in the Binary Tree
Similar to above, to find the maximum value, search to the right of the binary tree until the node’s right is null, indicating it is the maximum.
/**
* Find the maximum node in the binary tree
*/
maxNodeValue() {
let node = this.root;
if (node === null) {
return node;
}
while(node && node.right !== null) {
node = node.right;
}
return node.value;
}
Deleting Nodes
Define a removeNode method so it can be called on the tree instance.
/**
* Delete a node
* If the deleted node is n, find the successor s = min(n->right)
*/
removeNode(value) {
this.root = this[REMOVE_NODE_RECUSIVE](this.root, value);
}
Similarly, we need to define a REMOVE_NODE_RECUSIVE method for recursive calls. Removing a node is the most complex of the methods we implemented in the binary search tree. The code implementation is as follows, with comments provided as much as possible. The steps for the implementation are listed below:
- {1} First check if the node is null, if equal to null, return directly.
- {2} If the node to delete is less than the current node, search to the left of the tree
- {3} If the node to delete is greater than the current node, search to the right of the tree
- {4} Node found, divided into four cases
- {4.1} The current node has neither left nor right child, delete directly, return null
- {4.2} If the left child is null, it has a right child, change the reference of the current node to the right child’s reference, return the updated value
- {4.3} If the right child is null, it has a left child, change the reference of the current node to the left child’s reference, return the updated value
- {4.4} If neither left nor right child is null
/**
* Delete a node recursive call
* @param { Object } node
* @param { Number } value
*/
[REMOVE_NODE_RECUSIVE](node, value) {
// {1} If not found, return null directly
if (node === null) {
return node;
}
// {2} Recursively delete left node
if (value < node.value) {
node.left = this[REMOVE_NODE_RECUSIVE](node.left, value);
return node;
}
// {3} Recursively delete right node
if (value > node.value) {
node.right = this[REMOVE_NODE_RECUSIVE](node.right, value);
return node;
}
// {4} value === node.value Node found
// {4.1} The current node has neither left nor right child, delete directly, return null
if (node.left === null && node.right === null) {
node = null;
this.count--;
return node;
}
// {4.2} If the left child is null, it has a right child, change the reference of the current node to the right child's reference, return the updated value
if (node.left === null) {
node = node.right;
this.count--;
return node;
}
// {4.3} If the right child is null, it has a left child, change the reference of the current node to the left child's reference, return the updated value
if (node.right === null) {
node = node.left;
this.count--;
return node;
}
// {4.4} If neither left nor right child is null
// s = min(n->right)
if (node.left !== null && node.right !== null) {
// Find the minimum node, break the object reference, copy a new object s
const s = new this.CopyNode(this.minNode(node.right));
this.count++;
s.left = node.left;
s.right = this[REMOVE_NODE_RECUSIVE](node.right, s.value); // Delete the minimum node
node = null;
this.count--;
return s; // Return s node to replace the node
}
}
Limitations of Binary Search Trees
The same data with different insertion orders results in different trees. This is a problem with binary search trees; they may be unbalanced and not always a balanced binary tree. If inserted sequentially, the tree shape becomes like the right side, degenerating into a linked list. Imagine searching for node 40 in the tree shown on the right; it requires traversing all nodes, consuming twice the time compared to the left side.
To solve this problem, a balanced binary search tree may be needed, with common implementations including red-black trees, AVL trees, etc.
