Binary Tree Vs Binary Search Tree
Mehzabin Aothoi
We know that a tree is a non-linear data structure that represents hierarchical data and contains no cycles. Now, let's delve into a commonly asked question during interviews: When do we call a tree a binary tree, and how does it differ from a binary search tree?
What is a Binary Tree?
A tree containing at most 2 children is called a binary tree. That means every node can have 0-2 children. For instance, if we were to create a binary tree with [10, 20, 30, 40, 50, 60],
We can place the elements from 10-60.
We can also go in reverse order.
We can place the elements randomly as well. However we choose to place the elements, all three of the approaches correctly represent a binary tree.
What is a Binary Search Tree?
A binary search tree is essentially a type of binary tree. If a value is less than the value of the root node, it is added to the left subtree. Conversely, if the value is greater, it is added to the right subtree. So basically we iterate all the values and follow these steps,
Select root node
If value is less than root, add to left subtree
If value is greater than root, add to right subtree
Using the same values from previous example,
Binary Tree Vs Binary Search Tree
| Basis | Binary Tree | Binary Search Tree |
| Definition | A nonlinear data structure known as a Binary Tree is one in which each node can have a maximum of two child nodes | A BST is a binary tree with nodes that has right and left subtrees that are also binary search trees |
| Operations | Since Binary Trees are not ordered, the processes of inserting, deleting, and finding them take significantly more time | Due to their ordered characteristics, insertion, deletion, and searching of an element is faster in a BST than in a Binary Tree |
| Structure | There is no ordering in a Binary Tree in terms of how the nodes are arranged | In a BST, the left subtree contains elements that are less than the nodes element, while the right subtree contains elements that are greater than the nodes element |
| Data Representation | The representation of data is performed in a structure that is hierarchical | Data Representation is done in an ordered format |
| Duplicate Values | Duplicate values are permitted in binary trees | Duplicate values are not permitted in the Binary Search Tree |
| Complexity | O(n) | O(log n) |
Subscribe to my newsletter
Read articles from Mehzabin Aothoi directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
Mehzabin Aothoi
Mehzabin Aothoi
I am a Software Engineer based in Dhaka, Bangladesh. My goal is to always build elegant, scalable, and reliable applications. I am also enthusiastic about learning and adapting to the latest technology stacks and frameworks.