Maximum Width of a Binary Tree with a Null Value

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;
}

You can also try this code with Online C++ Compiler

Run Code

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: 

• Boundary Traversal Of Binary Tree
• Maximum Average of Subtree Values in a Given Binary Tree
• Maximum Level Sum in an N-Ary Tree
• Diameter of Binary Tree
• The Maximum Cost of Splitting Binary Tree into Two Halves

Happy Coding!