Difference Between Binary Tree and Binary Search Tree

Key Difference – Binary Tree vs Binary Search Tree
 

A data structure is a systematic way to organize data to use it efficiently. Arranging the data using the data structure should reduce the running time or the execution time. Also, the data structure should require a minimum amount of memory. Sometimes the data can be arranged in a tree structure. A tree represents a node connected by edges. The topmost node is the root. Each node can have a maximum of two nodes. They are known as child nodes. The node to the left of the parent node is the left child node while node to the right of the parent node is the right node.   The Binary Tree and Binary Search Tree are two tree data structures. A binary tree is a type of data structure where each parent node can have at most two child nodes. The binary search tree is a binary tree where the left child contains only nodes with values less than or equal to the parent node, and where the right child only contains nodes with values greater than to the parent node. That is the key difference. Unlike data structures such as arrays, the binary tree and binary search tree do not have an upper limit to store data.

CONTENTS

1. Overview and Key Difference
2. What is Binary Tree
3. What is Binary Search Tree
4. Similarities Between Binary Tree and Binary Search Tree
5. Side by Side Comparison – Binary Tree vs Binary Search Tree in Tabular Form
6. Summary

What is Binary Tree?

When arranging the data in a tree structure, the node at the top of the tree is known as the root node. There can only be one root for the whole tree. Any node except the root node has one edge upwards to a node. It is called the parent node. The node below the parent code is called its child node. Each parent node can have a maximum of two child nodes. They are referred as a left child node and right child node. A node without any child node is called a leaf node. There is no specific way to arrange data in the binary tree. There is a path from root node to each node.

Figure 01: Example of Binary Tree

Above is an example of a binary tree. The element 2, in the top of the tree, is the root. Each node has a maximum of two nodes. If a tree contains any loops or if one node contains more than two nodes, it cannot be classified as a binary tree. To go from one node to the other, there is always one path. The child nodes of root node 2 are 7 and 5. It is also possible for a node to have no nodes.  But any node cannot have more than two nodes. The right element of the root is 5. That element 5 is the parent node for child node 9. The node 4 and 11 have no child elements. Therefore, they are leaf nodes.

The binary tree is used to store data in hierarchical order. It is similar to the file structure of the computer. The data structure like an array can store a specific amount of data. But in a binary tree, there is no upper limit on the number of nodes.

What is Binary Search Tree?

A binary search tree is a binary tree data structure. Similar to a binary tree, the binary search tree also can have two nodes. Any node except the root node has one edge upwards to a node. It is called the parent node. The node below a given connected by its edge downward is called its child node. A node without any child node is called a leaf node. Each parent node can have a maximum of two nodes. There are child nodes referring a left child node and right child node. The topmost element is called the root node. The left child contains only nodes with values less than or equal to the parent node. The right child only contains nodes with values greater than or equal to the parent node.

Figure 02: Example of Binary Search Tree

The element 8 is the topmost element. Therefore, it is the root node. If 3 is a parent node, then 1 and 6 are child nodes. The 1 is the left child node while 6 is the right child node. The left child contains values less than or equal to the parent node. When 3 is the parent node, the left side should have an element which is less than or equal to 3. In this example, it is 1. The right child only contains nodes with values greater than the parent node. When 3 is the parent node, the right child node should have a higher value than 3. In this example, it is 6. Likewise, there is a certain order to arrange each data element a binary search tree. It is a data structure provides an efficient way to perform sorting, retrieving and searching data.

What are the Similarities Between Binary Tree and Binary Search Tree?

• Both Binary Tree and Binary Search Tree are hierarchical data structures.
• Both Binary Tree and Binary Search Tree have a root.
• Both Binary Tree and Binary Search Tree can have a maximum of two child nodes.

What is the Difference Between Binary Tree and Binary Search Tree?

Summary – Binary Tree vs Binary Search Tree 

A data structure is a way of organizing data. Sometimes the data can be arranged in a tree structure. Two of them are binary tree and the binary search tree. This article discussed the difference between binary tree and the binary search tree. A binary tree is a type of data structure where each parent node can have at most two child nodes. The binary search tree is a binary tree where the left child contains only nodes with values less than or equal to the parent node, and where the right child only contains nodes with values greater than the parent node.

Download the PDF of Binary Tree vs Binary Search Tree

You can download the PDF version of this article and use it for offline purposes as per citation note. Please download the PDF version here: Difference Between Binary Tree and Binary Search Tree

Reference:

1.Point, Tutorials. “Data Structures and Algorithms Tree.”, Tutorials Point, 8 Jan. 2018. Available here
2.Difference between Binary tree and Binary search tree. | javapedia.Net, Javapedia.net, 15 Feb. 2017. Available here

Image Courtesy:

1.’Binary tree’By Derrick Coetzee – Own work, (Public Domain) via Commons Wikimedia
2.’Binary search tree’By No machine-readable author provided.  (based on copyright claims)., (Public Domain) via Commons Wikimedia

Related posts:

Difference Between Stack and Queue Difference Between Hierarchical and Partitional Clustering Difference Between Arraylist and Vector Difference Between Schema and Table Difference Between Normalization and Denormalization