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:
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 h
as 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.
Must read: Learn excel online free!
Let us visualize this concept to get a clear understanding of Binary Search Trees.
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.
Explore our Popular Data Science Courses
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.
upGrad’s Exclusive Data Science Webinar for you –
How to Build Digital & Data Mindset
Our learners also read: Free Python Course with Certification
Top Data Science Skills to Learn
Top Data Science Skills to Learn
1
Data Analysis Course
Inferential Statistics Courses
2
Hypothesis Testing Programs
Logistic Regression Courses
3
Linear Regression Courses
Linear Algebra for Analysis
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.
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.
Read our popular Data Science Articles
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.
Learn data science courses online from the World’s top Universities. Earn Executive PG Programs, Advanced Certificate Programs, or Masters Programs to fast-track your career.
How can we traverse a Binary Search Tree?
Unlike linear data structures like arrays, linked lists, stacks, and queues, where we can traverse the data structure in a single way only, a Binary Search Tree gives us the liberty to traverse it in multiple ways. The most popular tree traversals are as follows: In an inorder traversal, we first traverse the left node of the tree, then the root node of the tree, and finally the right node of the tree. We follow the same fashion across all the subtrees as well. In a preorder traversal, we first traverse the root node of the tree and then the left and right node respectively. We follow the same fashion across all the subtrees as well. In a postorder traversal, we first traverse the left and right node of the tree respectively, and finally the root node of the tree. We follow the same fashion across all the subtrees as well.
What are the advantages and disadvantages of a BST?
The following are the advantages and disadvantages of a Binary Search Tree. The advantages are - Operations like insertion, deletion, and lookup can be performed in O(log n) time where n is the number of nodes. All the elements in a BST are sorted so we can easily traverse through a BST by simply using inorder traversal. BST can efficiently be used to design memory allocators to speed up the search process of memory blocks. The biggest disadvantage of a Binary Search Tree is that we must always use a balanced BST such as AVL and Red-Black Tree because if we do not use a balanced BST, our tree operations will not be performed in logarithmic time.
Differentiate between a full binary tree and a complete binary tree.
A full binary tree is a binary tree where all the nodes have child nodes between 0 and 2. In other words, a binary tree where all the nodes have at least 2 children nodes except leaf nodes is known as a full binary tree. On the other hand, a complete binary tree is a binary tree where every node is completely filled (exactly two children nodes) and the leaf nodes are located as left as possible.
