Binary Tree vs Binary Search Tree: Difference Between Binary Tree and Binary Search Tree

Introduction

Sorting is the process of arranging the data in a systematic order so that it can be analysed more effectively. The process of identifying a particular record is called searching. If the data is properly sorted in a particular order, then searching becomes an easy and efficient task. This article deals with one of the most important non-linear data structures, i.e., trees.

Trees are primarily used to represent data by demonstrating a hierarchical relationship between the elements. For example, table of contents, family tree. Technically, a tree may be defined as a finite set ‘T’ of one or more nodes such that a node is assigned as the root of the tree and the other nodes are divided into n>=0 disjoint sets T1, T2, T3, T4 …. Tn and are called as the subtrees or children of that root node.

What is a Binary Tree?

A binary tree is a non-linear data structure wherein a node can have either 0, 1 or 2 nodes. Each node in the binary tree is termed as either a parent node or as a child node. The topmost node of the Binary Tree is referred to as the root node. Each parent node can have at most 2 child nodes which are the left child node and the right child node.

A node in a binary tree has three fields:

Data Element – It stores the data value that is to be stored by the node.
Pointer to the left child – It stores the reference (or address) to the left-child node.
Pointer to the right child – It store the reference to the right-child node.

In this way, several nodes are combined together to build a Binary Tree.

A Binary Tree can be represented as:

Source

From the above figure, the root node 2 has two children (or child nodes), 7 and 5. 7 is referred to as the left-child node and 5 is called as the right-child node. In this way, each of the child nodes act as a parent node to several other nodes and together represent the Binary Tree.

Check out: Types of Binary Tree

Terminologies used in Binary Tree

Node: The basic representation of a termination point in a tree.

Root Node: The topmost node of a Binary Tree.

Parent Node: If a node is connected to another node through edges, it is known as a parent node. In a binary tree, a parent node can have a maximum of 2 child-nodes.

Child Node: If a node has a predecessor, it is known as child node.

Leaf Node: A node that does not have any child node is called as a leaf node.

Depth of a node: It is the distance from the root node to that particular node whose depth is to be measured.

Height of the tree: It is the longest distance from the root node to the leaf node.

These are a few basic terminologies of a Binary Tree. With this basic understanding of a Binary Tree, let us move on to an advancement of Binary Tree known as the Binary Search Tree.

Also Read: Binary Search Algorithm: Function, Benefits, Time & Space Complexity

What is a Binary Search Tree

As the name suggests, a Binary Search Tree or BST is a tree that is used in sorting, retrieving and searching data. It is also a type of non-linear data structure in which the nodes are arranged in a particular order. Hence, it is also called as “Ordered Binary Tree”. It has the following properties:

The left subtree of a node has nodes which are only lesser than that node’s key.
The right subtree of a node has nodes which are only greater than that node’s key.
Each node has distinct keys and duplicates are not allowed in Binary Search Tree.
The left and right subtree must also be a binary search tree.

Let us visualize this concept to get a clear understanding of Binary Search Trees.

Source

In the above figure, we see that the value of the root node is 8. With further scrutiny, it is observed that all the values in the left subtree are lesser than the value of the root node and all the values in the right subtree have values that are greater than the root node. Furthermore, it is noted that each value in the Binary Search Tree is unique and there are no duplicates. Thus, the properties of Binary Search Tree stated above are verified.

In yet another example, we see that though the left and right subtrees are binary search trees with unique values throughout the tree. The value at the leaf node in the left subtree is 12 which is greater than the root node value which is 12. Thus, this does not satisfy the property of the BST and hence, it is not a Binary Search Tree.

Search operation in a BST –

Consider a Binary Search Tree with the values given below. Let us understand how the search operation is performed to get 9 from the Binary Search Tree.

Source

In order to perform the binary search, we shall initially arrange all the integers in a sorted array. This is called as the search space. This search space shall consist of two pointers, called as the start and end pointers. The array of the above given Binary Search Tree is represented as:

The first step is to calculate the middle value of the array and compare it with the value that is to be searched, 9 in our case. This is done by calculating n/2, where n is the total number of elements in the array (BST) and it is 6. Thus, the 3rd element is the middle element which is 5.

Now that the middle element is compared with 9 and as it is not equal (greater), the searching operation will be performed on the right array. In this way, the search operation is reduced to half, as shown below:

In the next step, the middle element is calculated and is found to be 9, which matches our element to be searched.

Binary Tree vs Binary Search Tree –

Now that we have a basic understanding of both the Binary Tree and Binary Search Trees, let us quickly summarize some of the differences between both of them.

Basis for Comparison	Binary Tree	Binary Search Tree
Definition	A Binary Tree is a non-linear data structure in which a node can have 0, 1 or 2 nodes. Individually, each node consists of a left pointer, right pointer and data element.	A Binary Search Tree is an organized binary tree with a structured organization of nodes. Each subtree must also be of that particular structure.
Structure	There is no required organization structure of the nodes in the tree.	The values of left subtree of a particular node should be lesser than that node and the right subtree values should be greater.
Operations Performed	The operations that can be performed are deletion, insertion and traversal	As these are sorted binary trees, they are used for fast and efficient binary search, insertion and deletion.
Types	There are several types. Most common ones are the Complete Binary Tree, Full Binary Tree, Extended Binary Tree	The most popular ones are AVL Trees, Splay Trees, Tango Trees, T-Trees.

Conclusion

Thus, we infer that though both the Binary Tree and Binary Search Tree have a common hierarchical structure with a collection of nodes, they have several differences in their application. A Binary Tree is a basic structure with a simple rule that no parent must have more than 2 children whereas the Binary Search Tree is a variant of the binary tree following a particular order with which the nodes should be organized.

If you are curious to learn about Binary tree vs Binary search tree, check out IIIT-B & upGrad’s PG Diploma in Data Science which is created for working professionals and offers 10+ case studies & projects, practical hands-on workshops, mentorship with industry experts, 1-on-1 with industry mentors, 400+ hours of learning and job assistance with top firms.