Difference between binary tree and binary search tree
Binary trees and binary search trees are two different yet very crucial data structures. These are hierarchical data structures and are not linear. They are generally used in cases where a data group has some relation among them.
Let’s understand the differences between them.
What is a Binary tree?
A Binary Tree is a Data Structure having a root node and at most two children nodes. Each of these children forms the left subtree and the right subtree. The end nodes or the leaf nodes have no children and the left and right children of a leaf node are pointed by a NULL pointer.
In the above example, each node has either 0,1 or 2 children. Therefore, this tree is a binary tree.
What is a Binary Search Tree?
A BST is a type of tree data structure where for every node, all the nodes to the left of this node have a value lesser than the current node’s value. All the nodes to the right of this node have a value greater than the current node’s value, along with the fact that both the left subtree and the right subtree are Binary Search Trees. Both the left and the right subtrees are also BSTs.
Above is an example of the binary search tree. You can observe that each node has less than or equal to two children. And theleft child’s value is always lesser than the node’s value, and the right child’s value is always greater than the node’s value.
Differences between Binary tree and Binary search tree
|Binary Tree||Binary search tree|
|It is a non-linear data structure in which each node has less than or equal to two children, and each of the left and right subtrees should also be a binary tree.||It is a non-linear data structure in which each node has less than or equal to two children, and each of the left and right subtrees should also be a binary search tree.|
|Elements in this tree are in any random order.||Elements in this tree are in a fixed order. The order is that for each node, its left child should have a value less than its value, and the right child should have a value greater than the node’s value.|
|The elements in a binary tree are not ordered, and therefore, operations like searching, inserting, and deletion takes longer time, i.e., O(n) time to execute.||The elements in a binary search tree are ordered, and therefore, operations like searching, inserting, and deletion takes a shorter time, i.e., O(logn) time to execute.|
|There are four types of binary trees. These are Full Binary Tree, Complete Binary Tree, Perfect Binary Tree, and Extended Binary Tree.||There are three types of binary search trees. These are AVL trees, splay trees, and Tango trees.|
Frequently asked questions
- What is a binary tree?
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
- What is a binary tree used for?
In computing, binary trees are mainly used for searching and sorting as they provide a means to store data hierarchically.
- What are binary search trees?
Binary search trees are trees in which, for each node, the node’s value is larger than the maximum value in its left node and smaller than the minimum value in its right subtree.
- What is the difference between a graph and a tree data structure?
Both graph and tree data structures are hierarchical data structures. The difference between them is that a graph data structure can also contain cycles or self nodes. Whereas in a tree data structure, there are no cycles or self nodes.
In this article, we’ve discussed the differences between binary trees and binary search trees.
You can look for problems based on these. Some problems based on binary trees are a largest number in a binary tree, triplets in a binary tree, maximum depth of a binary tree, LCA of a binary tree, minimum depth in a binary tree, and height of the binary tree.
Some problems based on binary search trees are sorted linked list to balanced BST, BST iterator, convert BST to min-heap, BST iterator, predecessor and successor, flatten BST to a sorted list, and minimum swaps to convert the binary tree into BST.
To practice more such problems, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.