Difference between Binary Tree and Binary Search Tree

In this article, we will look at the difference between Binary Tree and Binary Search Tree. These topics are very important because these act as an underlying data structure for various other data structures. So, we will look at the description of each with examples and compare their properties.

Binary Tree

A Binary tree is a type of Tree data structure, Non-Linear (data is not contiguous or in sequence) in nature. It represents data in a hierarchical format. A binary tree like a regular tree comprises of nodes that are not Ordered. Each node in a binary tree can have a maximum of 2 child nodes. It can have 0,1 or 2 nodes. A node is represented as a parent or child node. A Parent node can have at most two children- Left Child and Right Child. The node which has at least two children is called Internal Node. Hence, each node in memory contains the following attributes:

• Data (Can be of any type).
• Left Pointer which has the reference for Left Child.
• Right Pointer which has the reference for Right Child.

Also Read: Difference between Tree and Graph Data Structure

Let us look at the following example:

In the above binary tree, you can see the tree is not ordered, the Node 1 is the root node. The left arrow and the right arrow indicate the left and right child of each node respectively. Nodes present at the last level are the leaf nodes. Hence, the given binary tree has Nodes 1, 2, 3 as the parent nodes. Node 1 and Node 2 are the internal nodes as they have 2 children.

Operations on Binary Tree with Complexities:

• Search: To search an element we need to traverse all nodes in the tree. With the assumption that we do Level Order Traversal for searching the time complexity to implement search is O(n) for n nodes in a tree.
• Insert: If we consider a Skewed Binary Tree, then inserting an element would require traversing to the last node of the tree then insert it. So the overall complexity will be O(n).
• Delete: For deleting a node we have to first search it in the tree then deallocate the memory. Thus, like the search operation, it also requires O(n) time.

Binary Search Tree

A Binary Search Tree (BST) is a special type of binary tree. It is a node based binary tree data structure where the nodes are arranged in a specific order. The nodes contain the same structure as in a binary tree but they differ in arrangements. It is an Ordered tree, which follows the given conditions:

• The left child of a node contains value or data less than it’s parent node.
• The right child of a node contains value or data greater than the parent node’s data.
• Hence, the left subtrees contain nodes with values lesser than the root of the tree and the right subtrees contain nodes with values greater than root of the tree.
• The left and the right subtrees of each node if they exist must also be a binary search tree and should follow the above rules. As each node’s data must be greater or lesser than it’s parent node so no nodes with Duplicate keys or values are allowed.

Below, a typical Binary Search Tree is shown:

In the above tree, you can see the tree is ordered. For every parent node, e.g. Node 7 (Root Node), it’s left child (Node 2) is smaller than it whereas it’s right child (Node 9) is greater than it. Each subtree of a node is itself  a binary search tree and follows the above rules.

Note: The In-Order traversal of the binary search tree will give the nodes in sorted order. The leftmost node has the smallest node value.

Operations on BST with Complexities:

The whole idea of using a BST or Binary Search Tree is to optimize the search operation for each lookup. If we search a Node in a BST we remove half sub-tree at every step because of it’s Ordered nature. For instance, consider a BST of n nodes, at each comparison we search for a node at either the left half or the right half. We reduce the search space to n/2 at each step until the element is found. The worst case for operations occurs in Skewed Binary Search Trees.

• Search: Searching for an element in a binary search tree generally takes O(log n) time or O(h), h is the height of the tree. In the worst case, the time taken to search an element is O(n) if the given BST is Skewed BST.
• Insert: The time is the same as search operation O(log n) or O(h) but in the worst case, it takes O(n) time.
• Delete: Overall complexity to search and deallocate memory is same as above O(log n) but in worst case O(n) time.

Now Let us look at the key differences between Binary Tree and a BST:

Binary Tree vs Binary Search Tree

That’s it for the article we looked at them in detail description of each with their examples along with the major differences.

Feel free to ask your doubts or to leave suggestions in the comment section below.