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.

Now that we have discussed what trees essentially are, let us delve into binary search tree and binary tree. They play crucial computational roles in software development. Binary trees permit nodes to have a maximum of two children, offering versatility in node arrangements without inherent ordering. However, a binary search tree (BST) is a specialized tree enforcing a specific order.

This structural distinction between binary tree and binary search tree greatly impacts functionality. BSTs excel in efficient search, insertion, and deletion due to their ordered layout, whereas binary trees offer more flexibility in organizing data hierarchies. 

Recognizing the difference between binary search tree and binary tree is vital for optimizing their use cases. Learn in detail about the difference between BST and BT in this blog.

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.

Binary trees can look different from one another. A balanced binary tree, also known as an AVL tree in Java, is well-proportioned, where the difference in the heights of the left and right parts of each node is small. The balanced structure os an AVL tree in data structure helps with faster searches and organized data. However, an unbalanced binary tree can be skewered, causing slower operations like searching and adding new data. 

A node in a binary tree has three fields:

Each node comprises three essential fields that define its structure and connections within the tree.

Data Element – It stores the data value that is to be stored by the node. 

It could represent any information the tree is designed to hold, such as numbers, strings, objects, or other types of data.

Pointer to the left child – It stores the reference (or address) to the left-child node. 

In computer memory, this pointer enables the node to link itself to its left child node. If a node doesn’t have a left child, this pointer typically holds a null value, indicating the absence of a left child.

Pointer to the right child – It store the reference to the right-child node. 

It helps establish the connection between the current node and its right child node. Like the left child pointer, if a node lacks a right child, this pointer usually holds a null value, signifying no right child node.

These pointers or references are fundamental in constructing the hierarchical structure of a binary tree. They establish relationships between parent nodes and their respective child nodes, enabling navigation through the tree from one node to another.

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

These pointers connect nodes based on their relationships (parent-child), helping organize a binary tree and implement traversal algorithms (like in-order, pre-order, or post-order traversal). This allows efficient access, manipulation, and management of data within the tree structure.

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

Understanding the terminologies used in a binary tree is fundamental to better grasp its structure and operations. Here’s a detailed list of these terms with their explanations:

Nodes are fundamental units within a tree data structure, representing individual elements or data points. Each node contains data (such as a value or an object) and pointers or references to its child nodes, if any. Nodes are interconnected through edges to form the hierarchical structure of the tree.

Root Node: The topmost node of a Binary Tree. 

The root node serves as the starting or entry point for accessing and traversing the entire tree structure. All other nodes are descendants of the root node, and its depth is always 0 as it is the starting point of the 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. 

Each parent node can have up to two child nodes, one positioned to its left and the other to its right in a binary tree.

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

They exist at the lowest level of the tree hierarchy and represent endpoints or final elements within the tree structure.

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

Depth signifies the number of edges traversed along the path from the root node to the target 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.

Understanding these terminologies provides a foundational understanding of the relationships between nodes and their positions within a binary tree. These concepts are essential in performing operations within the tree structure, such as traversal, searching, insertion, and deletion.

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:

Additionally, a crucial part of this tree structure is its ‘balanced’ nature, ensuring an even distribution of nodes. This enables efficient operations such as search, insertion, and deletion with time complexities typically near O(log n). 

A balanced binary search tree (BST) is a structured data representation that follows a hierarchical format, where each node can have a maximum of two children. In this tree, the left child of a node holds values smaller than the node, while the right child holds values greater than the node. 

All in all, a binary search tree is extensively used because it facilitates operational efficiency which aids in the ease of data management. It has the following properties:

• The left subtree of a node has nodes which are only lesser than that node’s key.

This property ensures that all nodes to the left of a parent node have values smaller than the parent node’s value, establishing a sorted order within the left subtree.

• The right subtree of a node has nodes which are only greater than that node’s key.

This property guarantees that all nodes to the right of a parent node have values larger than the parent node’s value, maintaining a sorted order within the right subtree.

• Each node has distinct keys and duplicates are not allowed in Binary Search Tree.

This ensures that no two nodes within the tree have the same key. This uniqueness facilitates unambiguous searching and retrieval of specific values within the tree. 

• The left and right subtree must also be a binary search tree.

Another critical property of a BST is that both the left and right subtrees of any node in the tree must also qualify as binary search trees. This recursive property ensures that the BST structure applies not only to the root node but to every subtree within the entire tree. Every sub-tree abides by the rules of a binary search tree, with its own left and right subtrees following the criteria of lesser and greater values, respectively.

The properties of a binary search tree (BST) make it ideal for organizing data. The left side of a node has smaller values, the right side has larger values, and no duplicates are allowed. Each part of the tree, whether left or right, follows these rules, too. Because of this arrangement, finding, adding, and removing items in a BST is faster and easier. These properties ensure a balanced and ordered arrangement of elements, enhancing the speed and efficiency of various operations performed on the tree.

Must read: Learn excel online free!

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.

upGrad’s Exclusive Data Science Webinar for you –

How to Build Digital & Data Mindset

Our learners also read: Free Python Course with Certification

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: Key Differences

A binary tree and a binary search tree differ mainly in how they organize their elements. In a binary tree, there’s no specific rule for arranging nodes. Each node can have at most two children, but there’s no particular order in which the elements are placed. 

This lack of ordering means that when you’re looking for something in a binary tree, you might have to check many nodes before finding what you need, which can take searching longer.

On the other hand, a binary search tree (BST) is all about order. It has a specific arrangement where the left child of a node holds values smaller than the node, and the right child holds values greater than the node. This organized structure makes searching much faster. 

For example, if you’re searching for a value, you can quickly decide whether to go left or right based on the comparison with the current node. This ordered arrangement significantly reduces the time it takes to find elements, making operations like search, insertion, and deletion faster and more efficient.

Because of these key distinctions between binary search tree vs binary tree, BSTs are commonly used in scenarios where quick retrieval based on an ordered arrangement is crucial, like in databases or symbol tables. They are excellent for tasks where finding specific values rapidly is essential. 

That being said, binary trees offer more flexibility and are used when ordered data is not the primary concern, such as in expression trees or file systems. Therefore, the core distinction between BST vs. binary tree lies in their organization method – one follows a specific order, while the other doesn’t – impacting how efficiently you can locate items within them.

Binary Tree vs Binary Search Tree – Table of Differences

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.

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.

The main binary search tree and binary tree difference boils down to their organization rules. A binary tree doesn’t follow a specific order, allowing nodes to have up to two children and offering flexibility. In contrast, a binary search tree arranges nodes so smaller values are on the left and larger ones on the right, making searching faster. 

Binary search trees work well for organized data tasks like in databases, while binary trees are more flexible for various data representation needs. Understanding these differences helps choose the right tree structure based on specific requirements.

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.