What is Binary Search Tree (BST)
A binary search tree (BST) is a type of binary tree that is used for searching and sorting data. It is called a “search tree” because it can be efficiently used to search for the presence or absence of a particular element in the tree. It is called a “binary” tree because each node has at most two children.
In a BST, the left child of a node is always less than the value of the node, and the right child is always greater than the value of the node.
This means that if we want to search for a particular value in the tree, we can start at the root node and then decide which direction to go based on whether the value we are looking for is less than or greater than the value of the current node. If the value is less than the current node, we go left; if it is greater, we go right. This process is repeated until we either find the value we are looking for or reach a null node, indicating that the value is not present in the tree.
One of the main benefits of using a BST is that it allows us to search for values in O(log n) time, where n is the number of nodes in the tree. This is much faster than searching through an unsorted list, which takes O(n) time.
Inserting and deleting elements from a BST is also relatively efficient. To insert a new element into the tree, we follow the same process as searching for a value, except that instead of stopping when we find the value we are looking for, we continue until we reach a null node. Then, we insert the new element as the left or right child of the node, depending on whether it is less than or greater than the value of the node. To delete a node from the tree, we need to find the node and then remove it while maintaining the BST property.
Here is an example implementation of a binary search tree class in JavaScript:
class TreeNode {
constructor(value) {
this.left = null
this.right = null
this.value = value
}
}
class BinarySearchTree {
constructor() {
this.root = null
}
insert(value) {
let newNode = new TreeNode(value)
if (!this.root) {
this.root = newNode
return
}
let curr = this.root
while (curr) {
if (value <= curr.value) {
if (curr.left) {
curr = curr.left
} else {
curr.left = newNode
break
}
} else {
if (curr.right) {
curr = curr.right
} else {
curr.right = newNode
break
}
}
}
}
lookup(value) {
if (!this.root) return "Empty Array"
let curr = this.root
while (curr) {
if (value === curr.value) {
return curr
} else if (value < curr.value) {
curr = curr.left
} else {
curr = curr.right
}
}
return "Not Found"
}
remove(value) {
if (!this.root) return "Empty Array"
let curr = this.root
let parentNode = null
while (curr) {
if (value < curr.value) {
parentNode = curr
curr = curr.left
} else if (value > curr.value) {
parentNode = curr
curr = curr.right
} else {
if (!curr.right) {
if (!parentNode) {
this.root = curr.left
} else {
if (curr.value < parentNode.value) {
parentNode.left = curr.left
} else if (curr.value > parentNode.value) {
parentNode.right = curr.left
}
}
} else if (!curr.right.left) {
if (!parentNode) {
this.root = curr.left
} else {
curr.right.left = curr.left
if (curr.value < parentNode.value) {
parentNode.left = curr.right
} else if (curr.value > parentNode.value) {
parentNode.right = curr.right
}
}
} else {
let leftmost = curr.right.left
let leftmostParent = curr.right
while (leftmost.left !== null) {
leftmostParent = leftmost
leftmost = leftmost.left
}
leftmostParent.left = leftmost.right
leftmost.left = curr.left
leftmost.right = curr.right
if (!parentNode) {
this.root = leftmost
} else {
if (curr.value < parentNode.value) {
parentNode.left = leftmost
} else {
parentNode.right = leftmost
}
}
}
}
}
}
}
const tree = new BinarySearchTree()
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)
console.log(tree.lookup(20))
/**
TreeNode {
left: TreeNode { left: null, right: null, value: 15 },
right: TreeNode { left: null, right: null, value: 170 },
value: 20
}
*/
console.log(tree.lookup(150)) // Not Found
console.log(JSON.stringify(traverse(tree.root)))
/**
* {"value":9,
* "left":{"value":4,"left":{"value":1,"left":null,"right":null}, "right":{"value":6,"left":null,"right":null}},
* "right":{"value":20,"left":{"value":15,"left":null,"right":null},"right":{"value":170,"left":null,"right":null}}}
*/
// 9
// 4 20
//1 6 15 170
function traverse(node) {
const tree = { value: node.value }
tree.left = node.left === null ? null : traverse(node.left)
tree.right = node.right === null ? null : traverse(node.right)
return tree
}
const maxDepth = function (root) {
if (!root) return 0
let maxDepth = 0
const helper = (root, depth) => {
if (root.left) helper(root.left, depth + 1)
if (root.right) helper(root.right, depth + 1)
if (!root.left) {
if (depth > maxDepth) maxDepth = depth
return
}
if (!root.right) {
if (depth > maxDepth) maxDepth = depth
return
}
}
helper(root, 1)
return maxDepth
}BSTs are commonly used in a variety of applications, such as
- Implementing associative arrays
- Representing mathematical expressions
- Storing data in databases.
- Algorithms for sorting and searching data, such as quicksort and merge sort.
Tree Traversal
Tree traversal is the process of visiting all the nodes in a tree in a specific order. There are three common types of tree traversal: inorder, preorder, and postorder.
Tree traversal is often used to perform some operation on all the nodes of a tree, such as printing the values of the nodes or evaluating a mathematical expression represented by the tree. It can also be used to create a copy of a tree or to delete all the nodes of a tree.
In order to implement tree traversal, we can use either a recursive or an iterative approach.
Let’s consider following BST as an example
Inorder traversal:
In an inorder traversal, we first visit the left child of a node, then the node itself, and then the right child. This means that the nodes of the tree are visited in the order: left child, root, right child.
function inorderTraversal(node) {
if (node !== null) {
inorderTraversal(node.left)
console.log(node.data)
inorderTraversal(node.right)
}
}For Above BST Inorder traversal array would be : [9,11,12,18,20,21,22]
Preorder traversal:
In a preorder traversal, we first visit the root node, then the left child, and then the right child. This means that the nodes of the tree are visited in the order: root, left child, right child.
function preorderTraversal(node) {
if (node !== null) {
console.log(node.data)
preorderTraversal(node.left)
preorderTraversal(node.right)
}
}For Above BST preorder traversal array would be : [18,11,9,12,21,20,22]
Postorder traversal:
In a postorder traversal, we first visit the left child, then the right child, and then the root node. This means that the nodes of the tree are visited in the order: left child, right child, root.
function postorderTraversal(node) {
if (node !== null) {
postorderTraversal(node.left)
postorderTraversal(node.right)
console.log(node.data)
}
}For Above BST preorder traversal array would be : [9,12,11,20,22,21,18]
It’s also possible to implement these tree traversal functions using an iterative approach rather than a recursive one. The iterative approach involves using a stack to keep track of the nodes that need to be visited. Here is an example of an iterative inorder traversal function:
function inorderTraversalIterative(root) {
const stack = []
let current = root
while (current !== null || stack.length > 0) {
while (current !== null) {
stack.push(current)
current = current.left
}
current = stack.pop()
console.log(current.data)
current = current.right
}
}Similar iterative approaches can be used for preorder and postorder traversal as well.
Conclusion
In conclusion, binary search trees (BSTs) are a type of binary tree data structure that are used for searching and sorting data. They are called search trees because they can be efficiently used to search for the presence or absence of a particular element in the tree, and they are called binary trees because each node has at most two children. BSTs are characterized by the property that the left child of a node is always less than the value of the node, and the right child is always greater than the value of the node. This allows us to search for values in O(log n) time, where n is the number of nodes in the tree. BSTs are also relatively efficient for inserting and deleting elements, making them a useful data structure for storing and manipulating data in a hierarchical manner.