Binary tree is a non-sequential or non-linear data structure used to represent hierarchical relationship among elements. You can add maximum two child nodes under any node of the binary tree. Binary Search Tree is basically a Binary Tree which follows these rules.
- All the nodes in the left subtree of a node have values smaller than the node
- All the nodes in the right subtree of the node have values bigger than the node.
Difference between Binary Tree and Binary Search Tree
Insertion in a Binary Tree
Nodes are added in a binary tree without following any specific pattern. To insert a node in binary tree you need to specify its parent and also how the node is related to the parent (left child or right child). So, insertion process is complex in case of binary tree since it involves finding the parent by any one traversal technique.
Insertion in a Binary Search Tree
Nodes are added in a binary search tree to maintain the pattern of BST. That is smaller nodes in the left subtree and bigger nodes in the right subtree. To insert a node in binary search tree you only need to specify the node to be inserted. A Search Operation will be first performed to find the location of the node that qualifies to become parent of the new node.
This is done by comparing nodes with the new node starting from the root node. If the new node is smaller than the current node, it must be added in the left subtree. If the new node is bigger than the current node, it must be added in the right subtree.
Deletion in a Binary Tree
To delete a node from the binary tree the tree has to be searched to find the location of this node and location of its parent. For this, any one traversal technique – Preorder, Postorder or Inorder, can be used to find the node to be deleted. Once the node is identified it can be deleted by updating the corresponding child pointer of its parent.
Deletion in a Binary Search Tree
Nodes can be deleted in a binary search tree by first searching the node to be deleted and identifying its parent. Search is performed by comparing a node with the node to be deleted beginning from the root node. If it is smaller than the current node, it will be present in the left subtree else it will be located in the right subtree.
This comparison and searching in either the left or right subtree continues till the node to be deleted is found. While doing this process the previous node is preserved in a separate pointer to maintain the information about the parent node of the current node.
Be First to Comment