Get this book -> Problems on Array: For Interviews and Competitive Programming

Today we are going to compare two non linear data structures binary trees and heaps since both are non liner there tend to be confusion regarding both of these usually we will try to remove these confusion.

See the summary table of differences at the end of this article

## Introduction

### Binary tree

A binary tree is a non-Linear data structure in which each node can have either 0, 1 or 2 child nodes each. Each node consists of

- Data portion
- Pointer to left child
- Pointer to right child

Depending upon how these nodes are arranged there are many kinds of Binary trees

- Full Binary Tree
- Complete Binary tree
- Perfect Binary tree
- Balanced Binary tree
- Skewed Binary tree

```
class BinaryTreeNode{
public:
int data;
BinaryTreeNode* left_child;
BinaryTreeNode* right_child;
};
```

### Heap

Heap is a special kind of tree based data structure in which it is a complete binary tree and it satisfies the heap property

- a node is always greater than its child nodes the key of root node is largest among all nodes this is the
**max heap property** - a node is always smaller than is child nodes and the key of the root node is smallest among all the nodes this is called the
**min heap property**

Rather than creting a class or struct a heap is usually represented using a linear data structure with random access such as vector or array where if the parent element lies at i^{th} then left child lies at 2*i+1 ^{th} index and right child lies at 2*i+2

^{th}index;

Whenever a operation is performed on heap it may loose its fundamental heap property to solve this problem we use a special function called the **heapify function** which restores the heap property.

```
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(vector<int> &heap, int i){
int s = heap.size();
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if(l < s && heap[l] > heap[largest])
largest = l;
if(r < s && heap[s] > heap[largest])
largest = s;
if(largest != i){
swap(&heap[i], &heap[largest]);
heapify(heap, largest);
}
}
```

Similarly we can change this to work for min heaps also.

## Difference in operations

Similar to any other data structure ob both heap and binary tree we can perform traversal, insertion and deletion

### Insertion

Since there is no ordering in binary treee we can insert a new node below any node with no more than 1 child already present

In binary tree can insert anywhere we want or trverse the tree levelwise and use a function to insert the node at first favourable position we see

```
BinaryTreeNode* InsertNode(BinaryTreeNode* root, int data){
if(root == nullptr){
auto* new_node = new BinaryTreeNode(data);
return new_node;
}
else {
queue<BinaryTreeNode *> q;
q.push(root);
while (!q.empty()) {
BinaryTreeNode *temp = q.front();
q.pop();
if (temp->left_child != nullptr)
q.push(temp->left_child);
else {
temp->left_child = new BinaryTreeNode(data);
return root;
}
if (temp->right_child != nullptr)
q.push(temp->right_child);
else {
temp->right_child = new BinaryTreeNode(data);
return root;
}
}
}
}
```

This function traverses the tree level by level and the fisr instanace that it gets a node with 1 or less children it inserts the new node below that node.

But, when we insert a new node into heap we need to maintain the heap property. So during insertion we just insert a new value into the heap vector or array and call the heapify function to maintain the heap property

```
void InsertHeap(vector<int> &heap, int data){
if(heap.empty()){
heap.push_back(data);
}
else{
heap.push_back(data);
for(int i = heap.size()/2 - 1; i >= 0; i--){
heapify(heap, i);
}
}
}
```

### Traversal

Since heap are stored in the form of linear data structure they can be traversed as is on the other hand on binary tree we can perform inorder, pre-order, post-order traversal. Lets learn about these traversals.

**Inorder Traversal**- first the left child is printed followed by parent and then right child**Post-order Traversal**- first the left and right child are printed followed by the parent node.**Pre-order Traversal**- First the parent node is printed followed by left and right childern of that node.

Inorder Traversal

- Traverse the left subtree
- Visit the root node
- Traverse the right sub tree

Postorder Traversal

- Traverse the left subtree
- Traverse the right sub tree
- Visit the node

Preorder Traversal

- Visit the node
- Traverse the left subtree
- Traverse the right sub tree

```
void Inorder(BinaryTreeNode* root){
if(root == nullptr){
return;
}
Inorder(root->left_child);
cout << root->data;
Inorder(root->right_child);
}
void Postorder(BinaryTreeNode* root){
if(root == nullptr){
return;
}
Postorder(root->left_child);
Postorder(root->right_child);
cout << root->data << " ";
}
void Preorder(BinaryTreeNode* root){
if(root == nullptr){
return;
}
cout << root->data;
Preorder(root->left_child);
Preorder(root->right_child);
}
```

Traversal of a heap

- Traverse and print the vector as is

```
void printHeap(const vector<int>& heap){
for(int i : heap){
cout << i << " ";
}
cout << endl;
}
```

### Deletion of a node

When we want to delete a node in bianry tree we need to take note that children of that node stay attached to the tree

- First we find the deepest rightmost node in the said tree and the node which we want to delete.
- swap the node to be deleted and rightmost node
- delete the node to be deleted now at the deepest rightmost position

```
void deleteLast(BinaryTreeNode* root, BinaryTreeNode* del){
queue<BinaryTreeNode*> q;
q.push(root);
BinaryTreeNode* temp = nullptr;
// traversing the tree and finding the node to be deleted
while(!q.empty()){
temp = q.front();
q.pop();
if (temp == del){
temp == nullptr;
delete(del);
return;
}
if (temp->right_child){
if(temp->right_child == del){
temp->right_child == nullptr;
delete(del);
return;
}
else{
q.push(temp->right_child);
}
}
if(temp->left_child){
if(temp->left_child == del){
temp->left_child == nullptr;
delete(del);
return;
}
else{
q.push(temp->left_child);
}
}
}
}
BinaryTreeNode* deleteLast(BinaryTreeNode* root, int x){
// Implementation for edge cases
if(root == nullptr){
return nullptr;
}
if(root->left_child == nullptr && root->right_child == nullptr){
if(root->data == x){
return nullptr;
}
else{
return root;
}
}
queue<BinaryTreeNode*> q;
q.push(root);
BinaryTreeNode* temp = nullptr;
BinaryTreeNode* Node = nullptr;
// traversing the tree and storing the required node in Node
while(!q.empty()){
temp = q.front();
q.pop();
if(temp->data == x){
Node = temp;
}
if(temp->left_child){
q.push(temp->left_child);
}
if(temp->right_child){
q.push(temp->right_child);
}
}
// now the last node is stored in temp and required node in Node
if(Node != nullptr){
int data_last = temp->data;
deleteLast(root, temp);
Node->data = data_last;
}
return root;
}
```

However The deletion from heaps is whole lot simpler. If the node to be deleted is leaf node we can simply delete the node. Else we can swap the node to be deleted with the last node and call the heapify function.

```
void deleteNode(vector<int> &heap, int x){
unsigned int s = heap.size();
unsigned int i;
for (i = 0 ; i < s ; i++){
if(x == heap[i])
break;
}
swap(&heap[i], &heap[s - 1]);
heap.pop_back();
for(int j = s/2 -1; j >= 0 ; j-- ){
heapify(heap, j);
}
}
```

## Applications

Both Heaps and Binary Trees have multitude of uses all aroud

Some major applications of Heaps are-

- Heaps are the practical implementation of priority queues as they enable us to not only push to the end of queues but lso to the middle of start of queue based on what the heapify function sorts the heap
- Heaps are essential in the implementation of Dijkstra's algorithm
- And obviously heaps are the basis of implementation of heap sort

On the other hand binary trees are probably the most important data structurethey form the bass of many other data structures even heaps the major applications of biary trees are the following

- Binary trees are used to maintain the routing tables in routers
- Binary trees are critical for binary search trees which are used when there is data constantly entering and leaving.
- Used in
**Binary Space Partition**an important concept in 3D games which determines which artifacts need to be rendered **Huffman Coding**is based on Binary trees which is itself a critical part of compressio algorithms used by .jpeg and .mp3 formats

Title |
Binary Tree |
Heap |
---|---|---|

Structure |
Binary Tree like any other Tree based data structure is represented using class having a data portion and pointers to its children. |
Heap Data stucture however is represented using a linear data stucture like an array or a vector where if the parent lies at i ^{th} postion then the children lie at2i + 1 ^{th} position and 2i + 2^{th}position |

Insertion |
Since there is no ordering in a binary tree hence a new node can be inserted below the first node from left in the bottom most level that does not have 2 children |
Since there is an ordering be it min or max heap we just append the new node to vector and call the heapify function to restore the heap order. |

Traversal |
we can traverse the binry tree in inorder, preorder and postorder format |
Heap can be only traversed linearly |

Deletion |
We swap the node to be deleted by the bottom rightmost node and then delete the bottom rightmost node |
We simply locate and delete the required node and call the heapify function to restore the heap order |

Application |
Maintain routing tables i routers, Heaps, Huffman coding and Binary search trees |
heaps are the practical implementation of priority queues and are important for implementation of Djikstras Algorithm and Heap sort. |

With this article at OpenGenus, you must have the complete idea of Heap and Binary Tree.