Currently Empty: ₹0.00
Binary Search Tree (BST) is an important data structure in computer science used for efficient data storage, searching, and retrieval. It belongs to the family of binary trees, where each node has at most two children, called the left child and the right child.
The key property of a BST is that for each node:
- All values in its left subtree are less than the node’s value.
- All values in its right subtree are greater than the node’s value.
This property helps in quickly locating data and performing operations such as insertion and deletion
What is Binary Search Tree ?
A binary search tree is a way to organize data in a tree-like structure. It starts with a root node, which is the top element of the tree. From the root, the tree splits into two parts called the left and right subtrees. The left subtree contains values that are smaller than the root, and the right subtree contains values that are larger than the root. Each node in the tree follows the same rule: its left child has smaller values than parent node, and its right child has larger values than parent node. This rule continues for all nodes in the tree.
Example of BST
In the above image, which is an example of a BST, the left subtree is smaller than the root and the right subtree is greater than the root. The values [10, 8, 5] in the left subtree are all smaller than 25, which is the root. The values [30, 28, 50] in the right subtree are all greater than the root.
Why use a Binary Search Tree?
Binary Search Trees are used because they allow us to perform three important operations quickly:
- Search for a value.
- Insert a new value.
- Delete an existing value.
When the tree is balanced (both left and right sub trees have almost equal height), all these operations take O(log n) time, which is much faster than searching one by one in an unsorted list.
Node of binary search tree follows order mentioned below
- The value of all nodes in the left sub-tree or left child should be lesser than its root node value.
- The value of all nodes in the right sub-tree or right child should be greater than or equal to its root value.
- Each node should follow the above two rules at every height of the Binary search tree i.e., we can say that this rule will be recursively applied to all the left and right sub-trees of the root.
Properties of BST
- Each node has at most two children: a left child and a right child.
- The left subtree of a node contains only values smaller than the node’s value.
- The right subtree of a node contains only values greater than the node’s value.
- Both the left and right subtrees are themselves BSTs.
- There are no duplicate nodes, each value in the tree is unique.
- The tree has a root node at the top from which all other nodes branch out.
- Searching, insertion, and deletion are faster if the tree is balanced, meaning the heights of left and right subtrees are almost equal.
BST Operations
Search
The search operation is used to find whether a particular element exists in the tree.
The following steps to implement the search operation are:
Step 1: Start at the root node
Every binary search tree (BST) has a special node called the root, which is the very first node of the tree. To search for any value, we always begin from the root node, because it is the top-most point of the tree and all other nodes branch out from it.
Step 2: Compare the value with the current node
Look at the value stored in the current node and compare it with the value you want to find. This comparison tells us what to do next.
Step 3: Check if the value matches
If the value you are searching for is equal to the current node, the element is found and the search is complete.
Step 4: Move to the left subtree if smaller
If the value you are searching for is smaller than the current node, then it must be in the left subtree (all smaller values are stored there). Move to the left child of the current node.
Step 5: Move to the right subtree if larger
If the value you are searching for is larger than the current node, then it must be in the right subtree (all larger values are stored there). Move to the right child of the current node.
Step 6: Repeat the process
Repeat steps 2–5 with the new current node until either the value is found or you reach a leaf node (a node with no children). If you reach a leaf node and the value is not found, it means the element is not in the tree.
Insert
The insert operation is used to add a new element to the binary search tree (BST) while keeping the BST property intact.
The following steps are used to implement the insert operation:
Step 1: Start at the root node
Every BST has a root node, which is the top-most node of the tree. To insert a new value, we always begin at the root.
Step 2: Compare the new value with the current node
Look at the value in the current node and compare it with the value you want to insert. This helps decide whether to move left or right.
Step 3: Move to the left subtree if smaller
If the new value is smaller than the current node, move to the left child. If the left child is empty, place the new value there.
Step 4: Move to the right subtree if larger
If the new value is larger than the current node, move to the right child. If the right child is empty, place the new value there.
Step 5: Repeat the process
Repeat steps 2–4 with the new current node until you find an empty spot where the new value can be inserted while maintaining the BST property.
Pre-order Traversal
The pre-order traversal is a way to visit all the nodes of a binary search tree (BST) in a specific order. In pre-order traversal, we visit the root first, then the left subtree, and finally the right subtree.
The following steps are used to perform pre-order traversal:
Step 1: Visit the root node
Start at the root node and process or print its value first. This is why it’s called “pre-order,” because the root is visited before its subtrees.
Step 2: Traverse the left subtree
Move to the left child of the root and perform pre-order traversal on the left subtree using the same steps.
Step 3: Traverse the right subtree
After finishing the left subtree, move to the right child and perform pre-order traversal on the right subtree.
Step 4: Repeat the process
Repeat steps 1–3 for each node until all nodes are visited.
In-order Traversal
The in-order traversal is a method to visit all the nodes of a binary search tree (BST) in a specific order. In in-order traversal, we visit the left subtree first, then the root node, and finally the right subtree.
The following steps are used to perform in-order traversal:
Step 1: Traverse the left subtree
Start at the root node and move to the left child. Perform in-order traversal on the left subtree first.
Step 2: Visit the root node
After completing the left subtree, process or print the value of the root node.
Step 3: Traverse the right subtree
Move to the right child of the root and perform in-order traversal on the right subtree.
Step 4: Repeat the process
Repeat steps 1–3 for each node until all nodes are visited.
Post-order Traversal
The post-order traversal is a way to visit all nodes of a binary search tree (BST). In post-order traversal, we visit the left subtree first, then the right subtree, and finally the root node.
The following steps are used to perform post-order traversal:
Step 1: Traverse the left subtree
Start at the root and move to the left child. Perform post-order traversal on the left subtree first.
Step 2: Traverse the right subtree
After finishing the left subtree, move to the right child and perform post-order traversal on the right subtree.
Step 3: Visit the root node
After both left and right subtrees are visited, process or print the value of the root node.
Step 4: Repeat the process
Repeat steps 1–3 for every node until all nodes are visited.
Advantages of using a binary search tree
- In a BST, while searching for an element, we get a clue at each step about whether to go left or right depending upon the comparison we make with the node value and the target value.
- In the best case for searching an element, it takes O(log2n) time, and in the worst case, it takes O(n) to search an element. This complexity is much better than the array and linked list for the same operation.
Conclusion
A Binary Search Tree (BST) is a type of tree where the left child is smaller and the right child is bigger than the parent. BSTs make it easy and fast to find, add, or remove items because we don’t have to check every node. They are useful in searching, sorting, and storing data efficiently. BSTs work best when the tree is balanced.
[wpusb]