Difference between Tree and Binary Tree
Tree Binary tree
A tree is a hierarchical data structure A binary tree is a specific type of tree in which
consisting of nodes connected by edges. Each each node has at most two child nodes: a left child
node can have any number of child nodes. and a right child.
In data structure, a tree can not be empty. While it can be empty.
In tree, a node can have at most n(number of While in binary tree, a node can have at
child nodes) nodes. most 2(number of child nodes) nodes.
While in binary tree, there is limitation on the
In tree, there is no limitation on the degree of
degree of a node because the nodes in a binary tree
a node.
can’t have more than two child node.
In tree, there is either zero subtree or many While in binary tree, there are mainly two
subtree. subtree: Left-subtree and Right-subtree.
Binary search tree
A Binary Search Tree (BST) is a binary tree where each node's left subtree contains values less than
the node, and the right subtree contains values greater than the node.
Advantages of Binary Search Tree (BST):
Efficient searching: O(log n) time complexity for searching with a self balancing BST
Ordered structure: Elements are stored in sorted order, making it easy to find the next or
previous element
Dynamic insertion and deletion: Elements can be added or removed efficiently
Balanced structure: Balanced BSTs maintain a logarithmic height, ensuring efficient operations
Doubly Ended Priority Queue: In BSTs, we can maintain both maximum and minimum
efficiently.
Example of creating a Binary Search Tree (BST)
Now, let's see the creation of binary search tree using an example.
Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50
o First, we have to insert 45 into the tree as the root of the tree.
o Then, read the next element; if it is smaller than the root node, insert it as the root of the
left subtree, and move to the next element.
o Otherwise, if the element is larger than the root node, then insert it as the root of the right
subtree.
Now, let's see the process of creating the Binary search tree using the given data element. The
process of creating the BST is shown below –
Step 1 - Insert 45.
Step 2 - Insert 15.
As 15 is smaller than 45, so insert it as the root node of the left subtree.
Step 3 - Insert 79.
As 79 is greater than 45, so insert it as the root node of the right subtree.
Step 4 - Insert 90.
90 is greater than 45 and 79, so it will be inserted as the right subtree of 79.
Step 5 - Insert 10.
10 is smaller than 45 and 15, so it will be inserted as a left subtree of 15.
Step 6 - Insert 55.
55 is larger than 45 and smaller than 79, so it will be inserted as the left subtree of 79.
Step 7 - Insert 12.
12 is smaller than 45 and 15 but greater than 10, so it will be inserted as the right subtree of 10.
Step 8 - Insert 20.
20 is smaller than 45 but greater than 15, so it will be inserted as the right subtree of 15.
Step 9 - Insert 50.
50 is greater than 45 but smaller than 79 and 55. So, it will be inserted as a left subtree of 55.
Now, the creation of binary search tree is completed. After that, let's move towards the
operations that can be performed on Binary search tree.
We can perform insert, delete and search operations on the binary search tree.
Let's understand how a search is performed on a binary search tree.
Searching in Binary search tree(BST)
Searching means to find or locate a specific element or node in a data structure. In Binary search
tree, searching a node is easy because elements in BST are stored in a specific order. The steps of
searching a node in Binary Search tree are listed as follows -
1. First, compare the element to be searched with the root element of the tree.
2. If root is matched with the target element, then return the node's location.
3. If it is not matched, then check whether the item is less than the root element, if it is
smaller than the root element, then move to the left subtree.
4. If it is larger than the root element, then move to the right subtree.
5. Repeat the above procedure recursively until the match is found.
6. If the element is not found or not present in the tree, then return NULL.
Now, let's understand the searching in binary tree using an example. We are taking the binary
search tree formed above. Suppose we have to find node 20 from the below tree.
Step1:
Step2:
Step3:
Deletion in Binary Search tree(BST)
In a binary search tree, we must delete a node from the tree by keeping in mind that the property
of BST is not violated. To delete a node from BST, there are three possible situations occur -
o The node to be deleted is the leaf node, or,
o The node to be deleted has only one child, and,
o The node to be deleted has two children
When the node to be deleted is the leaf node
It is the simplest case to delete a node in BST. Here, we have to replace the leaf node with NULL
and simply free the allocated space.
We can see the process to delete a leaf node from BST in the below image. In below image,
suppose we have to delete node 90, as the node to be deleted is a leaf node, so it will be replaced
with NULL, and the allocated space will free.
When the node to be deleted has only one child
In this case, we have to replace the target node(Deleting node) with its child, and then delete the
child node. It means that after replacing the target node with its child node, the child node will
now contain the value to be deleted. So, we simply have to replace the child node with NULL
and free up the allocated space.
We can see the process of deleting a node with one child from BST in the below image.
In the below image, suppose we have to delete the node 79, as the node to be deleted has only
one child, so it will be replaced with its child 55.
So, the replaced node 79 will now be a leaf node that can be easily deleted.
When the node to be deleted has two children
This case of deleting a node in BST is a bit complex among other two cases. In such a case, the
steps to be followed are listed as follows -
o First, find the inorder successor of the node to be deleted.
o After that, replace that node with the inorder successor until the target node is placed at
the leaf of tree.
o And at last, replace the node with NULL and free up the allocated space.
The inorder successor is required when the right child of the node is not empty. We can obtain
the inorder successor by finding the minimum element in the right child of the node.
We can see the process of deleting a node with two children from BST in the below image. In the
below image, suppose we have to delete node 45 that is the root node, as the node to be deleted
has two children, so it will be replaced with its inorder successor. Now, node 45 will be at the
leaf of the tree so that it can be deleted easily.
Now let's understand how insertion is performed on a binary search tree.
Insertion in Binary Search tree(BST)
A new key in BST is always inserted at the leaf. To insert an element in BST, we have to start
searching from the root node; if the node to be inserted is less than the root node, then search for
an empty location in the left subtree. Else, search for the empty location in the right subtree and
insert the data. Insert in BST is similar to searching, as we always have to maintain the rule that
the left subtree is smaller than the root, and right subtree is larger than the root.
Now, let's see the process of inserting a node into BST using an example.
The complexity of the Binary Search tree
Let's see the time and space complexity of the Binary search tree. We will see the time
complexity for insertion, deletion, and searching operations in best case, average case, and worst
case.
1. Time Complexity
Operations Best case time Average case Worst case time
complexity time complexity complexity
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)
Worst case scenario indicates the BST is the Degenerated BST for all the operations (insertion,
deletion and search)
Where 'n' is the number of nodes in the given tree.
2. Space Complexity
Operations Space complexity
Insertion O(n)
Deletion O(n)
Search O(n)
o The space complexity of all operations of Binary search tree is O(n).