Binary Tree
A tree is considered a binary tree if it satisfies the following conditions:
At most two ( 2 ) children (may have fewer)
Exactly one root
Exactly one path between the root and any node
Empty tree can be considered as binary tree
This tree is a binary tree because each node contains at most two (2) children.
For more clarification, see Figure 2.
In the above figure, Node A contains two pointers: a left pointer and a right pointer, pointing to the left and right nodes. Node B contains both left and right nodes. Nodes D, E, and F point to NULL.
Binary Search Tree
A binary tree is considered a BST if it satisfies the following conditions:
left subkeys are less than the root key
Right subkeys are greater than the root key
The left and right subtrees must be binary search trees.
No duplicates
In the above binary search tree , each node follows a specific order. The value of the left node must be smaller than the root node, and the value of the right node must be greater than the root node. This rule applies recursively to the entire tree, including the left and right subtrees of the root.
Suppose we have some data: 50, 15, 69, 89. From this data, we need to create a binary search tree.
The first element or data always becomes the root of the BST.
First, we need to insert 50 into the tree as the root of the binary search tree.
Then, compare the second data, 15, with the root node. If it is smaller than the root node, insert it on the left side of the root node.
Then, compare the third data, 69, with the root node. If it is greater than the root node, insert it on the right side of the root node.
89 is greater than 50 and 69.then it will we inserted as the right subtree.
The creation of the binary search tree is complete.
We've covered the theory part, so let's jump to the code. This part is more interesting than the theory part.
First, we are going to create an empty Binary Search Tree (BST).
class BSTNode {
constructor(key) {
this.key = key
this.left = null
this.right = null
}
}
The BSTNode class creates a node for the tree. Each node has a value (key) and two links (left and right) that point to other nodes.
key: The value stored in the node.left: This will point to the left child node (nodes with smaller values).right: This will point to the right child node (nodes with larger values).
class BinarySearchTree{
constructor() {
this.root = null
}
}
The BinarySearchTree class defines a structure for creating a binary search tree.
this.root = null means that when we create a binary search tree, it starts off empty. The root is the top node of the tree, and currently, the tree has no nodes.
Insertion in Binary Search Tree
Insertion in a BST can be performed by following the steps given below:
If the root is null, simply add the newNode, and it becomes the root of the tree. Then, the left and right of this node will point to null.
If there is already a root present, check if the new node is less than the root. If it is, add it to the left side. If not, add it to the right side of the root.
Otherwise, check if the item is less than the root element of the tree. If it is, recursively perform this operation with the left subtree of the root.
If the new node is not less than the root, perform this operation recursively with the right subtree of the root.
class BinarySearchTree {
constructor() {
this.root = null;
}
// Inserts a new key into the binary search tree
insert(key) {
const newNode = new BSTNode(key);
// If the root is null, the new node becomes the root
if (this.root === null) {
this.root = newNode;
} else {
// Otherwise, insert the node in the correct position
this.insertNode(this.root, newNode);
}
}
// Helper method to insert a node in the correct position
insertNode(node, newNode) {
// If the new node's key is less than the current node's key, go to the left subtree
if (newNode.key < node.key) {
// If there is no left child, place the new node here
if (node.left === null) {
node.left = newNode;
} else {
// If there is a left child, recursively call insertNode on the left child
this.insertNode(node.left, newNode);
}
} else { // If the new node's key is greater than or equal to the current node's key, go to the right subtree
// If there is no right child, place the new node here
if (node.right === null) {
node.right = newNode;
} else {
// If there is a right child, recursively call insertNode on the right child
this.insertNode(node.right, newNode);
}
}
}
}
Deletion in Binary Search tree
We have three cases to delete a node.
First is deleting a leaf node.
In this case, replace the leaf node with NULL.
For example, if we want to delete node 4, since node 4 is a leaf node, it will be replaced with NULL.
Second, the node to be deleted has only one child
Replace the node with its child and delete the child node. The child node now contains the value to be deleted, so simply replace it with NULL.
For example, if we want to delete node 9, which has only one child, we replace node 9 with its child node.
Third, the node to be deleted has two child nodes.
In this case, the node to be deleted is replaced with its in-order successor (smallest key in right subtree). This is done recursively until the node value to be deleted is moved to a leaf. After that, replace the node with NULL.
For example, replace 15 with its in-order successor 18. Now, 15 will be moved to the leaf of the tree, which will then be deleted.
class BinarySearchTree {
constructor() {
this.root = null;
}
// Method to delete a key from the BST
delete(key) {
this.root = this.deleteNode(this.root, key);
}
// Helper method to delete a node with a specific key
deleteNode(node, key) {
// If the node is null, return null
if (node === null) {
return null;
}
// If the key to be deleted is smaller than the current node's key, go left
if (node.key < key) {
node.left = this.deleteNode(node.left, key);
// If the key to be deleted is greater than the current node's key, go right
} else if (node.key > key) {
node.right = this.deleteNode(node.right, key);
// If the key is found
} else {
// If the node has no children, return null
if (node.left === null && node.right === null) {
return null;
// If the node has no left child, return the right child
} else if (node.left === null) {
return node.right;
// If the node has no right child, return the left child
} else if (node.right === null) {
return node.left;
// If the node has two children
} else {
// Find the minimum value in the right subtree
const tempNode = this.findMinValue(node.right);
// Replace the node's key with the minimum value found
node.key = tempNode.key;
// Delete the node with the minimum value in the right subtree
node.right = this.deleteNode(node.right, tempNode.key);
}
}
// Return the (possibly updated) node
return node;
}
// Helper method to find the minimum value in a subtree
findMinValue(node) {
// Go left until finding the leftmost node
while (node.left !== null) {
node = node.left;
}
// Return the leftmost node (minimum value)
return node;
}
}
We write the same logic, but this time we use the in-order predecessor. The only difference is finding the smallest key in the left subtree.
For example, replace 15 with its in-order predecessor 12. Now, 15 will be moved to the leaf of the tree, which will then be deleted.
class BinarySearchTree {
constructor() {
this.root = null;
}
// Method to delete a key from the BST
delete(key) {
this.root = this.deleteNode(this.root, key);
}
// Helper method to delete a node with a specific key
deleteNode(node, key) {
// If the node is null, return null
if (node === null) {
return null;
}
// If the key to be deleted is smaller than the current node's key, go left
if (node.key > key) {
node.left = this.deleteNode(node.left, key);
// If the key to be deleted is greater than the current node's key, go right
} else if (node.key < key) {
node.right = this.deleteNode(node.right, key);
// If the key is found
} else {
// If the node has no children, return null
if (node.left === null && node.right === null) {
return null;
// If the node has no left child, return the right child
} else if (node.left === null) {
return node.right;
// If the node has no right child, return the left child
} else if (node.right === null) {
return node.left;
// If the node has two children
} else {
// Find the maximum value in the left subtree
const tempNode = this.findMaxValue(node.left);
// Replace the node's key with the maximum value found
node.key = tempNode.key;
// Delete the node with the maximum value in the left subtree
node.left = this.deleteNode(node.left, tempNode.key);
}
}
// Return the (possibly updated) node
return node;
}
// Helper method to find the maximum value in a subtree
findMaxValue(node) {
// Go right until finding the rightmost node
while (node.right !== null) {
node = node.right;
}
// Return the rightmost node (maximum value)
return node;
}
}
Pre-order
Here's how pre-order traversal works:
Visit the root node.
Recursively traverse the left subtree.
Recursively traverse the right subtree.
class BinarySearchTree {
constructor() {
this.root = null;
}
// Method to perform a post-order traversal of the BST
postorder() {
let result = [];
this.postOrder(this.root, result);
return result;
}
// Helper method to recursively perform a post-order traversal
postOrder(node, result) {
// If the node is null, return
if (node === null) {
return;
}
// Recur on the left child
this.postOrder(node.left, result);
// Recur on the right child
this.postOrder(node.right, result);
// Process the current node
result.push(node.key);
}
}
In-order
Recursively traverse the left subtree.
Visit the root node.
Recursively traverse the right subtree.
class BinarySearchTree {
constructor() {
this.root = null;
}
// Method to perform an in-order traversal of the BST
inorder() {
let result = [];
this.inOrder(this.root, result);
return result;
}
// Helper method to recursively perform an in-order traversal
inOrder(node, result) {
// If the node is null, return
if (node === null) {
return;
}
// Recur on the left child
this.inOrder(node.left, result);
// Process the current node
result.push(node.key);
// Recur on the right child
this.inOrder(node.right, result);
}
}
post-order
Recursively traverse the left subtree.
Recursively traverse the right subtree.
Visit the root node.
class BinarySearchTree {
constructor() {
this.root = null;
}
// Method to perform a post-order traversal of the BST
postorder() {
let result = [];
this.postOrder(this.root, result);
return result;
}
// Helper method to recursively perform a post-order traversal
postOrder(node, result) {
// If the node is null, return
if (node === null) {
return;
}
// Recur on the left child
this.postOrder(node.left, result);
// Recur on the right child
this.postOrder(node.right, result);
// Process the current node
result.push(node.key);
}
}
