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.

Frequently Asked Questions

  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!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think