In this article, we will see basic and important difference between binary tree and binary search tree. Let us understand both with an examples.
- 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
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.
- 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.