Implementing a Binary Search Tree in JavaScript
In this post, we’ll explore how to implement a basic Binary Search Tree (BST) in JavaScript. We’ll cover inserting nodes and performing different tree traversal methods—in-order, pre-order, and post-order.
The Node Class
First, let’s define a Node class to represent each node in the tree:
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
Each Node object has three properties:
- value: The data stored in the node.
- left: A pointer to the left child node.
- right: A pointer to the right child node.
The BinarySearchTree Class
Next, we’ll define a BinarySearchTree class that will manage the nodes and provide methods to interact with the tree:
class BinarySearchTree {
constructor() {
this.root = null;
}
isEmpty() {
return this.root === null;
}
insertNode(root, newNode) {
if(newNode.value < root.value) {
if(root.left === null) {
root.left = newNode;
} else {
this.insertNode(root.left, newNode);
}
} else {
if(root.right === null) {
root.right = newNode;
} else {
this.insertNode(root.right, newNode);
}
}
}
search(root, value) {
if(!root) {
return false;
}
if(root.value === value) {
return true;
} else if(root.value > value) {
return this.search(root.left, value);
} else {
return this.search(root.right, value);
}
}
insert(value) {
const newNode = new Node(value);
if(this.isEmpty()) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
}
}
Key Methods:
- isEmpty(): Checks if the tree is empty.
- insertNode(root, newNode): Inserts a new node into the tree, maintaining the binary search tree property.
- search(root, value): Recursively searches for a value in the tree.
- insert(value): A convenient method to insert a new value into the tree.
Tree Traversal Methods
Once we have a tree, we often need to traverse it. Here are the three common traversal methods:
In-order Traversal
In-order traversal visits the nodes in the following order: Left, Root, Right.
inOrder(root) {
if(root) {
this.inOrder(root.left);
console.log(root.value);
this.inOrder(root.right);
}
}
This traversal prints the nodes in non-decreasing order for a binary search tree.
Pre-order Traversal
Pre-order traversal visits the nodes in the following order: Root, Left, Right.
preOrder(root) {
if(root) {
console.log(root.value);
this.preOrder(root.left);
this.preOrder(root.right);
}
}
This traversal is useful for copying the tree structure.
Post-order Traversal
Post-order traversal visits the nodes in the following order: Left, Right, Root.
postOrder(root) {
if(root) {
this.postOrder(root.left);
this.postOrder(root.right);
console.log(root.value);
}
}
This traversal is often used for deleting or freeing nodes.
Example Usage
Let’s see how these methods work together:
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(20);
bst.insert(3);
bst.insert(7);
console.log('In-order Traversal:');
bst.inOrder(bst.root);
console.log('Pre-order Traversal:');
bst.preOrder(bst.root);
console.log('Post-order Traversal:');
bst.postOrder(bst.root);
Conclusion
With this implementation, you can now create and interact with a Binary Search Tree in JavaScript. Understanding tree structures and traversal methods is crucial for many algorithmic problems, especially in areas like search algorithms, parsing expressions, and managing hierarchical data.
Top comments (0)