Organizations can use different data structures to organize and store data in multiple forms. Data structures include different values, multiple functions, and their relationships to apply to data and function with certain algorithms. A binary search tree is a form of data structure, and you can learn all about it from this article.
What is Binary Search Tree in Data Structure?
A binary search tree includes nodes arranged in a predetermined sequence. The value of the root in a binary search tree is higher than the value of the nodes in the left sub-tree. Meanwhile, the root’s value usually equals or exceeds all the nodes in the right subtree.
A binary search tree in data structures can be expressed as:
Get curriculum highlights, career paths, industry insights and accelerate your technology journey.
Download brochure
Types of Binary Search Tree
A Binary Search Tree(BST) is a binary tree in which each node has at most two children. The left child is always smaller than the parent, while the right child is greater. Based on their structure and balancing techniques, there are different types of BSTs.
Standard Binary Search Tree(BST):
The basic form of a BST is where each node follows the left< root < right property.
This data structure lacks balancing mechanisms, which allows the tree to become twisted like a linked list when sorted data is inserted.
Self Balancing BSTs:
These BSTs automatically balance themselves to maintain optimal search time O(log n).
AVL Tree: This tree uses height balancing, which ensures that the height difference between the left and right subtrees is at most 1.
Red-Black Tree: A BST with an additional property with either red or black nodes, ensuring balanced tree height.
Splay Tree: A self-adjusting BST moves frequently accessed nodes closer to the root.
Treap: A combination of BST and heap, where nodes have keys (BST property) and priorities (heap property) to maintain balance.
The Anatomy of Binary Search Trees
The different components of a binary search tree in the data structure are as follows:
Nodes: Nodes refer to a termination point in any binary search tree in data structures.
Roots: The node on top of a binary tree is called the root.
Leaf Node: The external nodes with no child are called the leaf nodes.
Internal Node: All inner nodes with at least one child node are called internal nodes.
Parent: Apart from the root, all other nodes of the binary tree with at least one subnode are parents.
Child: The node rising straight from the parent node is the child.
Edge: An edge can indicate a relationship between two nodes by connecting them.
Depth Height of a Tree: The root or tree height signifies the highest number of edges from the farthest lead node to the edges.
How Binary Search Trees Work?
The binary search tree data structure can support different basic operations like:
Search
Insert
Find minimum
Find maximum
Delete
Find the kth smallest element
Find successor
Find predecessor
The operations come with an O(h) time complexity, where h signifies the tree’s height.
A balanced binary search tree includes the same number of nodes on the right and left subtrees of the root. The above operations in a balanced binary tree in a data structure require O(log n) time (n= number of nodes in the tree). Meanwhile, the time required for operations in a linear binary search tree will be O(n).
On average, a randomly built binary search tree in a data structure has a height of O(log n). Therefore, the basic operations on such a tree will take approximately O(log n) time.
You can only insert a new element in a binary search tree at the leaf. We should begin searching from the root node to add an element to a binary search tree. When the inserting node has a lesser value than the root, we will look for an empty location in the left subtree.
But when the value of the data element is higher than the node, we will look for a space in the right subtree to insert a new element. Maintaining the property of the binary tree during insertion is crucial.
Deletion in Binary Search Tree
We can’t violate its fundamental property while performing deletion in a binary search tree. Binary search trees can be deleted under the following circumstances:
The leaf node is the target. We can replace the designated space with NULL to empty it.
The target node comes with a single child: We can replace the target node with the child and later delete the child node.
The target node has two children. First, we must find the successor of the node we wish to delete. Then, as long as the target node is on the leaf, we can replace it with the successor. Ultimately, we should replace the target node with NULL to empty the allocated space.
Searching in Binary Search Tree
A binary tree in data structures can help you search for a specific node or element. The steps to perform a search in a binary tree are as follows:
Compare the element to be searched with the tree’s root value.
If the root’s value is the same as the target element, return the node’s location.
If the root’s value does not match the target element, check if the target is smaller or greater than the root element. Move to the right subtree if the root element is smaller and to the right if the root element is greater.
Continue with the procedure until you find a match.
Return NULL if you can’t find the target element in the tree
Implementation of Binary Search Tree
The binary search tree in data structures gets implemented in the following steps:
Step 1: Read the user’s search element.
Step 2: Look for the middle element in the sorted list.
Step 3: Use the middle element in the sorted list to compare the search element.
Step 4: When both get matched, it shows “Given element is found!!!” The function also gets terminated.
Step 5: When the elements don’t match, it’s necessary to determine whether the search element is larger or smaller than the middle element.
Step 6: When the search element is smaller than the middle element, steps 2, 3, 4 and 5 for the middle element’s left sublist become necessary.
Step 7: When the search element is larger than the middle element, steps 2, 3, 4, and 5 must be repeated for the middle element’s right sublist.
Step 8: If that element fails to match the search element, it shows “Element is not found in the list!!!” After that, the function gets terminated.
The following programs show the binary search tree in data structure example
// Class representing a Node in BST
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
// Class for Binary Search Tree
class BinarySearchTree {
Node root;
// Constructor
BinarySearchTree() {
root = null;
}
// Insert a new key into the BST
void insert(int key) {
root = insertRec(root, key);
}
// Recursive function to insert a new key
Node insertRec(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
return root;
}
// Inorder traversal (Left, Root, Right)
void inorder() {
inorderRec(root);
}
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
// Main function to test BST
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
// Inserting nodes
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);
// Print inorder traversal (sorted order)
System.out.println("Inorder traversal of BST:");
tree.inorder();
}
}
Complexity Analysis of Binary Search Tree Operations
Time Complexity
Operation
Best Case
Average Case
Worst Case
Insertion
O(log n)
O(log n)
O(n)
Deletion
O(log n)
O(log n)
O(n)
Search
O(log n)
O(log n)
O(n)
Space Complexity
Operation
Space Complexity
Insertion
O(n)
Deletion
O(n)
Search
O(n)
Applications of Binary Search Tree Data Structure
Binary search trees (BSTs) are widely used in various applications due to their efficiency in searching, inserting, and deleting operations, all running on average in O(log n) time.
Searching and Sorting: BSTs support rapid element lookup operations that make them beneficial for quick lookup applications. The sorting technique Tree Sort depends on them together with other algorithms.
Database Indexing: The BSTs are used in database indexing structures like B-Trees and AVL Trees, which help in efficient data retrieval.
Symbol Table Management: The compilers and interpreters, BSTs, help manage symbol tables, allowing fast lookup of variable names, functions, and keywords.
Auto-Complete and Spell Checking: The BST-based structures like ternary search trees are used for auto-suggestion and spell-checking systems.
Networking Routing Algorithms: The BSTs help in efficient routing table management in networking applications.
Artificial Intelligence and Decision Trees: The BSTs are fundamental in decision tree-based machine learning algorithms and AI systems.
Memory Management: The BSTs, especially balanced BSTs like AVL trees or Red-Black trees, are used in memory allocation to manage free blocks efficiently.
A Binary Search Tree (BST) is a special type of binary tree that maintains its elements sorted, making search, insertion, and deletion operations efficient. Let’s discuss some of its advantages.
Efficient Searching: Binary search operations in a BST Take O(log n) time in a balanced tree, making it significantly faster than linear search in an unsorted list O(n).
Fast Insertion and Deletion: Binary Search Tree insertion and deletion also take O(log n) time in a balanced BST. The structure order allows elements to be quickly placed or removed while maintaining the BST properties.
Inorder Traversal Yields Sorted Order: Performing an inorder traversal (left-root-right) on a BST gives an element in ascending order. This makes it useful in applications requiring sorted data retrieval without additional sorting.
A Binary Search Tree (BST) is a hierarchical data structure for efficient searching, insertion, and deletion operations. However, it has several disadvantages, especially when not properly balanced.
Unbalanced Tree Problem: Sorted element insertion can transform a BST into a structure that resembles a linked list, resulting in O(n) time complexity instead of O(log n) for searching and other operations.
More Memory Usage: Each node requires extra memory to store pointers for its left and right child nodes, making BSTs less memory-efficient than arrays or hash tables.
Poor Cache Performance: Each node requires extra memory to store pointers for left and right child nodes, making BSTs less memory-efficient than or hash tables.
Conclusion
The Binary Search Tree (BST) is a crucial data structure that enables fast searching, insertion, and deletion operations. It is widely used in real-world applications like databases, search engines, and file systems. While BST provides efficient operations in a balanced state, unbalanced trees can degrade performance. Advanced variations like AVL Trees and Red-Black Trees help maintain balance for optimal performance. Understanding BSTs is essential for improving problem-solving skills in data structures and algorithms.
Binary search trees are non-linear data structures with a maximum of two children for every parent node. The different types of binary search trees include full, complete, perfect, degenerate, and balanced.
What are the Binary Search Tree Complexities?
In both the average and the worst cases, the space complexity of a binary search is O ( n ) O(n) O(n).
What is a perfect binary tree?
The internal nodes of a perfect binary tree have a maximum of two children. Moreover, every lead node remains at the same level within the binary search tree.
Can a binary search tree be linear?
A binary search tree cannot be linear. Understand the difference between Linear Search vs. Binary Search.
When to use Binary Tree Data Structure?
Binary search trees are particularly useful for sorting and searching because they store data hierarchically.
What is a Binary Search tree in data structure
A binary search tree (BST) is a specified form of a binary tree in data structure, where each node follows a specific ordering rule.
The left subtree, of a node contains only nodes with values less than the node’s key.
The right subtree of a node contains only nodes with values greater than the node ‘s key.
Both the left and right subtree must also be binary search trees.
