# Maximum Width of a Binary Tree with a Null Value

## Introduction

Trees enable us to organize information in a hierarchical method. This data structure differs greatly from linear data structures such as linked lists or arrays. A tree is made up of nodes that contain information.

Tree-based questions are increasingly becoming very common in programming interviews. Therefore it is necessary to master questions based on trees and their applications to ace technical interviews of big companies.

## Problem Statement

We are given a Binary Tree consisting of N nodes. Our task is to find the maximum width of the given Binary Tree. ​​The maximum width of the tree is the maximum width among all the levels of the given tree.

The width of a level here is defined as the distance between the level's leftmost and rightmost non-null nodes, with null nodes between the leftmost and rightmost being also included in the length computation.

Example:

Input:

Assume we have the following tree as input:

``````                   1
/  \
2    3
/ \      \
4   5      8
/ \
6   7``````

Output:

``4``

Explanation:

The width at the first level is 1

The width at second level is 2

The width at the third level is 4 (null node between 5 and 8 also counted)

The width at the fourth level is 2

So maximum width id maximum of 1,2,4,2 which is 4.

## 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.

1. 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.

2. 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.

3. What is Complexity Analysis of Queue operations?
For a queue, insertion and deletion are both O(1) operation wheres access and searching takes O(N) time.

## Key Takeaways

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

Happy Coding! 