What is Binary Tree?
Binary Tree is a hierarchical data structure in which each node has zero, one, or at the most, two children. Each node contains a “left” pointer, a “right” pointer, and a data element. The “root” pointer represents the topmost node in the tree. Each node in the data structure is directly connected to arbitrary number of nodes on either side, referred to as children. A null pointer represents the binary tree. There is no particular order to how the nodes are to be organized in the binary tree. Nodes with no children nodes are called leaf nodes, or external nodes.
In simple terms, it defines an organized labeling function on the nodes, which in turn assign some random value to each node. Anything which has two children and one parent node is a binary tree. Binary trees are used to store information that forms a hierarchy like the file system on your personal computer. Unlike Arrays, Trees have no upper limit on the number of nodes because they are linked using pointers, like Linked Lists. Main functions of Binary Tree include representing hierarchical data, sorting data lists, providing efficient insert/delete operations, etc. Tree nodes are represented using structures in C.
What is Binary Search Tree?
A Binary Search Tree is a type of binary tree data structure in which the nodes are arranged in order, hence also called as “ordered binary tree”. It’s a node-based data structure which provides an efficient and fast way of sorting, retrieving, searching data. For each node, the elements in the left subtree must be less than or equal to the key in its parent node (L<P), and the elements in the right subtree must be greater than or equal to the key in its parent node (R>P). There should be no duplicate keys. In simple terms, it’s a special kind of binary tree data structure that efficiently stores and manages items in memory.
It allows for fast access of information, insertion and removal of data, plus it can be used to implement lookup tables which allow for searching items by their unique keys, like searching for a person’s phone number by name. The unique keys are sorted in an organized manner, so that lookup and other dynamic operations could be performed using binary search. It supports three main operations: searching of elements, insertion of elements, and deletion of elements. Binary Search Tree allows for fast retrieval of elements stored in the tree as each node key is thoroughly compared with the root node, which discards half of the tree.
Difference Between Binary Tree and Binary Search Tree
- Definition of Binary Tree and Binary Search Tree – Binary Tree is a hierarchical data structure in which a child can have zero, one, or maximum two child nodes; each node contains a left pointer, a right pointer and a data element. There’s no particular order to how the nodes should be organized in the tree. Binary Search Tree, on the other hand, is an ordered binary tree in which there is a relative order to how the nodes should be organized.
- Structure of Binary Tree and Binary Search Tree– The topmost node in the tree represents the root pointer in a binary tree, and the left and the right pointers represent the smaller trees on either side. It’s a specialized form of tree which represents data in a tree structure. Binary search tree, on the other hand, is a type of binary tree in which all the nodes in the left subtree are less than or equal to the value of the root node and that of the right subtree are greater than or equal to the value of the root node.
- Operation of Binary Tree and Binary Search Tree– Binary tree can be anything that has two children and one parent. Common operations that can be performed on a binary tree are insertion, deletion, and traversal. Binary search trees are more of sorted binary trees that allows for fast and efficient lookup, insertion, and deletion of items. Unlike binary trees, binary search trees keep their keys sorted, so lookup usually implements binary search for operations.
- Types of Binary Tree and Binary Search Tree– There are different types of binary trees, the common being the “Full Binary Tree”, “Complete Binary Tree”, “Perfect Binary Tree”, and “Extended Binary Tree”. Some common types of binary search trees include T-trees, AVL trees, Splay trees, Tango trees, Red-Black trees etc.
Binary Tree vs. Binary Search Tree: Comparison Chart
| Binary Tree | Binary Search Tree |
| Binary Tree is a specialized form of tree which represents hierarchical data in a tree structure. | Binary Search Tree is a type of binary tree which keeps the keys in a sorted order for fast lookup. |
| Each node must have at the most two child nodes with each node being connected from exactly one other node by a directed edge. | The value of the nodes in the left subtree are less than or equal to the value of the root node, and the nodes to the right subtree have values greater than or equal to the value of the root node. |
| There is no relative order to how the nodes should be organized. | It follows a definitive order to how the nodes should be organized in a tree. |
| It’s basically a hierarchical data structure that is a collection of elements called nodes. | It’s a variant of the binary tree in which the nodes are arranged in a relative order. |
| It is used for fast and efficient lookup of data and information in a tree structure. | It is mainly used for insertion, deletion, and searching of elements. |
Summary of Binary Tree and Binary Search Tree
While both simulate a hierarchical tree structure representing a collection of nodes with each node representing a value, they are quite different from each other in terms of how they can be implemented and utilized. A Binary Tree follows one simple rule that each parent node has no more than two child nodes, whereas a Binary Search Tree is just a variant of the binary tree which follows a relative order to how the nodes should be organized in a tree.