## Approach

We know that a binary tree can be represented by an array (assume the root begins from the position with index 1 in the array). If the index of a node is i, the indices of its two children, left child, and right child is 2*i and 2*i + 1 respectively. The idea is to use a queue to record the indices of the leftmost node and rightmost node in each level, respectively. For each level of the tree, the width is last - first+ 1. Then, we just need to find the maximum width.

In order to perform a level traversal, we would be using a queue. To know more about level traversal you can visit Level Order Traversal.

### Code

```
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int item)
{
val = item;
left = right = NULL;
}
} TreeNode;
int widthOfBinaryTree(TreeNode* root) {
if(!root)
return 0;
int ans = 0;
queue<pair<TreeNode*, int>> q;
q.push({root,0});
while(!q.empty()){
int size = q.size();
int mmin = q.front().second;
int first,last;
for(int i=0; i<size; i++){
int cur_id = q.front().second-mmin;
TreeNode* node = q.front().first;
q.pop();
if(i==0)
first = cur_id;
if(i==size-1)
last = cur_id;
if(node->left)
q.push({node->left, cur_id*2});
if(node->right)
q.push({node->right, cur_id*2+1});
}
ans = max(ans, last-first+1);
}
return ans;
}
int main()
{
/*
Constructed binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
*/
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->right = new TreeNode(8);
root->right->right->left = new TreeNode(6);
root->right->right->right = new TreeNode(7);
cout<<widthOfBinaryTree(root);
return 0;
}
```

Output

`4`

### Complexity Analysis

Time Complexity: O(N)

Where N is the number of nodes of the tree. Because we iterated each node once.

Space Complexity: O(W)

Where W is the maximum width of the tree. Because at any time, we will be having all the nodes of a level in the queue.

## Frequently Asked Questions

### What is a Binary Tree?

A binary tree is a non-linear data structure of the tree type, with a maximum of two offspring for each parent. Along with the data element, every node in a binary tree has a left and right reference. The root node is the node at the top of a tree's hierarchy.

### What is a leaf node?

Any node in a Binary Tree that has zero children, or in other words both left and right children are null is called Leaf Node.

### What is the Complexity Analysis of Queue operations?

For a queue, insertion and deletion are both O(1) operation whereas access and searching takes O(N) time.

## Conclusion

A tree is basically a collection of nodes linked together by edges. These 'trees' constitute a tree-like data structure, with the 'root' node leading to 'parent' nodes, which lead to 'children' nodes.

Endpoints with no child nodes are known as 'leaf' nodes. Because of their non-linear form, trees serve a vital role in data structures. This results in a speedier reaction time during a search and more convenience during the design process.

If you wish to practice more Tree related problems, you can visit TOP TREES INTERVIEW QUESTIONS

Recommended Reading:

Happy Coding!