Question:
Given a binary tree root node, get the maximum width of that tree
Example:
Consider the image given below
Width at level 1 is 1. Because it has only 1 node.
Width at level 2 is 2. Because it has only 2 nodes.
Width at level 3 is 4. Because it has only 4 nodes.
Solution:
While doing level order traversal, compute the number of nodes at each level.
Then get the max of nodes at each level and display the result.
Solution
#include <iostream> #include <queue> #include <stack> using namespace std; // structure to hold binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; int get_max_width(Node *root) { if (root == NULL) return 0; int result = 0; queue<Node*> q; q.push(root); while (!q.empty()) { //get the size of the queue int count = q.size() ; result = max(count, result); //this loop will get all the nodes at a particular level while (count > 0) { Node *temp = q.front(); q.pop(); if (temp->left != NULL) q.push(temp->left); if (temp->right != NULL) q.push(temp->right); count --; } } return result; } int main() { Node* root = nullptr; /* Binary tree: 16 / \ / \ 10 25 / \ / \ / \ / \ 7 15 18 30 */ root = new Node(16); root->left = new Node(10); root->right = new Node(25); root->left->left = new Node(7); root->left->right = new Node(15); root->right->left = new Node(18); root->right->right = new Node(30); cout<<"The max width of the binary tree is = "<< get_max_width(root)<<endl; return 0; }
Output:
The max width of the binary tree is = 4