Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Code
3.2.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a Binary Tree?
4.2.
What is a leaf node?
4.3.
What is the Complexity Analysis of Queue operations?
5.
Conclusion
Last Updated: Mar 27, 2024

Maximum Width of a Binary Tree with a Null Value

Author Rhythm Jain
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

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 with 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 the 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 the maximum width id a maximum of 1,2,4,2 which is 4.

Recommended: Try The Problem Yourself First Before Moving on to the Solution.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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!

Previous article
Convert a given tree to its Sum Tree
Next article
Check if Binary Tree Contains a Balanced BST of Size K
Live masterclass