In this article, we will see basic and important difference between binary tree and binary search tree. Let us understand both with an examples.
What is Binary Tree ?
- A binary tree is a non linear data structure that is defined as a collection of elements called nodes.
- In a binary tree, the topmost element is called the root node, and each node has 0, 1, or at the most 2 children.
- A node that has zero children is called a leaf node or a terminal node. Every node contains a data element, a left pointer which points to the left child, and a right pointer which points to the right child. The root element is pointed by a ‘root’ pointer. If root == NULL, then it means the tree is empty.
- In a Binary Tree, there is no particular order in which nodes are arranged in binary tree.
Linked List Representation
- In the linked representation of a binary tree, every node will have three parts: the data element, a pointer to the left node, and a pointer to the right node.
- So in C, the binary tree is built with a node type given below.
- Every binary tree has a pointer ROOT, which points to the root element (topmost element) of the tree. If ROOT = NULL, then the tree is empty.
Linked List Implementation of Binary Tree
What is Binary Search Tree ?
A binary search tree, also known as an ordered binary tree, is a variant of binary trees in which the nodes are arranged in an order.
- A tree is called Binary Search Tree (BST) if it satisfy following two conditions:
- All nodes must have at most two children. (Binary tree)
- In a binary search tree, all the nodes in the left sub-tree have a value less than that of the root node. Correspondingly, all the nodes in the right sub-tree have a value either equal to or greater than the root node.
Binary Search Tree
- The nodes in a Binary Search Tree are ordered. So the time needed to search an element in the tree is greatly reduced.
- Operatons on Binary Search Tree : Searching Data, Inserting Data, Deleting Data, Traversing the Tree
- Retrieval of data from Binary Search Tree is very fast because desired data can be compared with the value of root node, which discards half of the tree.
- Representation of Binary Search Tree node in memory with linked list is same as Binary Tree node.
Difference between Binary Tree and Binary Search Tree ?
- Meaning of Binary Tree and Binary Search Tree:
Binary Tree is a non linear hierarchical data structure in which an any node can have zero, one, or at most two children; every node contains a three things : Data part, Left pointer and Right pointer. There is no specific manner in which nodes are stored in binary tree. On the other hand, Binary Search Tree is an arranged or organized binary tree where there is a specific order in which all nodes are arranged in BST.
- Structure of Binary Tree and Binary Search Tree :
The root node in the tree pointed by root pointer in a binary tree, and the left and right pointers point to the left and right smaller subtrees without any specific order. On the other hand, Binary Search tree is a kind of binary tree wherein values of all the nodes in the left subtree are smaller than the value of the root node and that of the values of nodes in the right subtrees are greater than or equivalent to the value of the root node.
- Operations on Binary Tree and Binary Search Tree :
Binary tree can be whatever has at most two children and one parent. Normal tasks that can be performed on a binary tree are insertion of node, deletion of node, searching of node, and traversal of nodes. Binary search trees are a greater amount of arranged binary trees that takes into consideration quick and proficient searching of nodes, insertion, and deletion of nodes. In contrast to binary trees, binary search trees keep their values arranged, so lookup generally executes binary search for operations.
Tree traversals algorithms :
Binary tree and Binary search tree are having same tree traversal algorithms
- Pre-Order Traversal
- In-Order Traversal
- Post-Order Traversal
- Kinds of Binary Tree and Binary Search Tree :
Various types of binary trees are “Full Binary Tree”, Complete Binary Tree, Threaded Binary Tree, Extended Binary Tree. On the other side, types of binary search trees are “AVL Tree”, “2-3 Tree”, “B-Tree”, “Red-Black Tree” etc.