Binary Tree vs Binary Search Tree: Data Structure

Difference Between Binary Tree and Binary Search Tree

What is Binary Tree?

A tree which each node can have utmost two children called binary tree. These children are referred as the ‘left child’ and the ‘right child’ of the parent node. We can say a binary tree is a non-linear data structure. In binary tree, no order is preserved so it takes more time for performing the operations.

In binary tree, a node contains three fields with it:

• Address of the left child: A node contains the reference of its left child.
• Address of the right child: A node contains the reference of its right child.
• Data item: A node also contains the value of data item.

                                      BinaryTree

Binary Tree Representation

We can implement the binary tree using two ways:                                                                                                          

1. Using arrays:

We can use an array to store the nodes of binary tree. The nodes are stored in contiguous memory location that can be accessed sequentially.

2. Using linked list:

The binary tree can be implemented by linked list and its every element referred as nodes contains three fields i.e., left child, right child and data value of the node.

Binary Tree Terminologies: -

• The first node of the tree is called root node of the tree.
• A node has child nodes is called internal node.
• A node that has no child is called leaf node.
• The longest distance from the root node to the leaf node is called height of the tree
• The number of edges from the node to the tree's root node is called the depth of the node.

The Time Complexity of Binary Tree

The operations of binary tree (i.e., insertion, deletions and searching) take O (n) time.

What is Binary Search Tree?

The binary search tree is a kind of binary tree data structure and it follows the conditions of binary tree. As we know, in binary tree a node has utmost two children so this same condition followed by binary search tree. In addition, a binary search tree has some other properties as follows:

• In binary search tree, the left sub - tree of any node contains only smaller elements than the node element.
• In binary search tree, the right sub - tree of any node contains only greater elements than the node element.
• The left sub-tree and the right sub - tree must also be following the properties of binary search tree.

The Time Complexity of Binary Search Tree

If we talk about operations of binary search tree take O (log n) time. The time complexity of these operations could be O(n) if the binary search tree skewed (if the input to the binary search tree comes in an ascending or descending manner).

Binary Search Tree Key Difference: -

Binary Tree	Binary Search Tree
A tree is said to be a binary tree where every node of it contains utmost two children.	Binary search tree is another type of binary tree. It also follows same condition of binary tree.
A binary tree doesn’t follow any order so the operations like insertion, deletion or searching takes more time to perform.	Binary search tree stores the elements into sorted order so operations take less time to perform.
Some types of binary trees are Complete Binary Tree, Perfect Binary Tree, Full Binary Tree.	Some another type of binary search trees such as Splay trees, AVL tree etc.