A binary search tree (BST) is a type of data structure used to store a collection of items, such as numbers or strings, in a way that allows for efficient searching, insertion, and deletion operations.
A BST is composed of nodes that contain a key and two pointers, one to the left child and one to the right child. The key of each node is unique and can be compared to other keys in the tree.
The tree is constructed such that for each node, all the keys in its left subtree are smaller than its own key, and all the keys in its right subtree are greater than its own key. This property ensures that the tree is ordered, and enables efficient searching and other operations.
Operations of Binary Search Tree
A binary search tree (BST) is a data structure that supports the following operations:
Insertion
Given a key, insert a new node containing that key into the tree. Starting at the root of the tree, we compare the key to the current node's key. If the key is less than the current node's key and the left child is empty, we add the new node as the left child of the current node. If the key is greater than the current node's key and the right child is empty, we add the new node as the right child of the current node. If the key is equal to the current node's key, we replace the current node's value with the new value. If the left or right child is not empty, we continue the process recursively with the left or right child.
// Define the node class
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Define the BST class
class BST {
constructor() {
this.root = null;
}
// Insert a new node in tree
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
} else {
let current = this.root;
while (true) {
if (value === current.value) {
return undefined;
}
if (value < current.value) {
if (!current.left) {
current.left = newNode;
return this;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
}
}
// Create a binary search tree and insert some nodes
const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
bst.insert(12);
bst.insert(17);
Search
Given a key, search for the node containing that key. Starting at the root of the tree, we compare the key to the current node's key. If the key is less than the current node's key, we move to its left child. If the key is greater than the current node's key, we move to its right child. We continue this process until we find the node containing the key or reach a leaf node.
// Define the node class
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Define the BST class
class BST {
constructor() {
this.root = null;
}
// Insert a new node in tree
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
} else {
let current = this.root;
while (true) {
if (value === current.value) {
return undefined;
}
if (value < current.value) {
if (!current.left) {
current.left = newNode;
return this;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
}
// search a node value in tree
search(value) {
if (!this.root) {
console.log("Root Node does not exist!!");
} else {
let current = this.root;
while (true) {
if (value === current.value) {
return console.log(`${value} value found!!`);
}
if (value < current.value) {
if (!current.left) {
return console.log(`${value} value not found!!`);
}
current = current.left;
} else {
if (!current.right) {
return console.log(`${value} value not found!!`);
}
current = current.right;
}
}
}
}
}
// Create a binary search tree and insert some nodes
const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
bst.insert(12);
bst.insert(17);
// Perform search operation and display the results
bst.search(7);
7 value found!!
Traversal
Traverse the nodes of the tree in a specific order.
There are three types of traversal:
a. In-order traversal: Traverse the left subtree, visit the node, and traverse the right subtree.
b. Pre-order traversal: Visit the node, traverse the left subtree, and traverse the right subtree.
c. Post-order traversal: Traverse the left subtree, traverse the right subtree, and visit the node.
See my Tree Traversal Blog Here!!
Finding minimum and maximum
Find the minimum (or maximum) value in the tree. Starting at the root, we follow the left (or right) child until we reach a leaf node.
// Define the node class
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Define the BST class
class BST {
constructor() {
this.root = null;
}
// Insert a new node in tree
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
} else {
let current = this.root;
while (true) {
if (value === current.value) {
return undefined;
}
if (value < current.value) {
if (!current.left) {
current.left = newNode;
return this;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
}
// find a min node value in tree
findMin() {
if (!this.root) {
console.log("Root Node does not exist!!");
} else {
let current = this.root;
while (true) {
if (current.left) {
current = current.left;
} else {
return console.log(`${current.value} is the minimun value!!`);
}
}
}
}
// find a max node value in tree
findMax() {
if (!this.root) {
console.log("Root Node does not exist!!");
} else {
let current = this.root;
while (true) {
if (current.right) {
current = current.right;
} else {
return console.log(`${current.value} is the maximum value!!`);
}
}
}
}
}
// Create a binary search tree and insert some nodes
const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
bst.insert(12);
bst.insert(17);
// Perform findMin operation and display the results
bst.findMin();
// Perform findMax operation and display the results
bst.findMax();
3 is the minimun value!!
17 is the maximum value!!
These operations can be implemented efficiently in a well-balanced BST, where the height of the tree is O(log n), where n is the number of nodes in the tree. In the worst-case scenario, where the tree is highly unbalanced, the height can be O(n), and the operations take O(n) time.
Summarizing Up
A binary search tree (BST) is a data structure that stores a set of elements in a tree-like structure. In a BST, each node has at most two children, referred to as left and right children, and the left child is always less than the parent, while the right child is always greater than the parent. This property makes it easy to search, insert, and delete elements in the tree efficiently, as they can be compared and navigated based on their values. BSTs are commonly used for implementing dictionaries, sets, and other applications that require efficient search, insertion, and deletion of elements. However, the performance of a BST depends on the shape of the tree, and in the worst case, it can degenerate into a linked list, leading to poor performance. Balancing techniques like AVL trees and red-black trees can be used to maintain a balanced BST and ensure optimal performance.