Maximum Width using Level Order Traversal
To get the width of each level we can use the level order traversal. The maximum among the width of all levels is the required answer.
Level Order Traversal without queue:
This method mainly involves two functions:
- One is to count nodes at a given level (getWidth), and
- The other is to get the maximum width of the tree(getMaxWidth). getMaxWidth() makes use of getWidth() to get the width of all levels starting from the root.
Given below are the pseudo-codes for the mentioned functions.
getMaxWidth(tree)
maxWdth = 0
for i = 1 to height(tree)
width = getWidth(tree, i);
if(width > maxWdth)
maxWdth = width
return maxWidthgetWidth(tree, level)
if tree is NULL then return 0;
if level is 1, then return 1;
else if level greater than 1, then
return getWidth(tree->left, level-1) +
getWidth(tree->right, level-1);
Below is the implementation of the above idea:
// C++ program to calculate width of binary tree
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node {
public:
int data;
node* left;
node* right;
node (int d){
this->data = d;
this->left = this->right = NULL;
}
};
/*Function prototypes*/
int getWidth(node* root, int level);
int height(node* node);
/* Function to get the maximum width of a binary tree*/
int getMaxWidth(node* root)
{
int maxWidth = 0;
int width;
int h = height(root);
int i;
/* Get width of each level and compare
the width with maximum width so far */
for (i = 1; i <= h; i++) {
width = getWidth(root, i);
if (width > maxWidth)
maxWidth = width;
}
return maxWidth;
}
/* Get width of a given level */
int getWidth(node* root, int level)
{
if (root == NULL)
return 0;
if (level == 1)
return 1;
else if (level > 1)
return getWidth(root->left, level - 1)
+ getWidth(root->right, level - 1);
}
/* UTILITY FUNCTIONS */
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(node* node)
{
if (node == NULL)
return 0;
else {
/* compute the height of each subtree */
int lHeight = height(node->left);
int rHeight = height(node->right);
/* use the larger one */
return (lHeight > rHeight) ? (lHeight + 1)
: (rHeight + 1);
}
}
/* Driver code*/
int main()
{
node* root = new node(1);
root->left = new node(2);
root->right = new node(3);
root->left->left = new node(4);
root->left->right = new node(5);
root->right->right = new node(8);
root->right->right->left = new node(6);
root->right->right->right = new node(7);
/*
Constructed binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
*/
// Function call
cout << "Maximum width is " << getMaxWidth(root)
<< endl;
return 0;
}
// This code is contributed by rathbhupendra
// C program to calculate width of binary tree
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node {
int data;
struct node* left;
struct node* right;
};
/*Function prototypes*/
int getWidth(struct node* root, int level);
int height(struct node* node);
struct node* newNode(int data);
/* Function to get the maximum width of a binary tree*/
int getMaxWidth(struct node* root)
{
int maxWidth = 0;
int width;
int h = height(root);
int i;
/* Get width of each level and compare
the width with maximum width so far */
for (i = 1; i <= h; i++) {
width = getWidth(root, i);
if (width > maxWidth)
maxWidth = width;
}
return maxWidth;
}
/* Get width of a given level */
int getWidth(struct node* root, int level)
{
if (root == NULL)
return 0;
if (level == 1)
return 1;
else if (level > 1)
return getWidth(root->left, level - 1)
+ getWidth(root->right, level - 1);
}
/* UTILITY FUNCTIONS */
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node)
{
if (node == NULL)
return 0;
else {
/* compute the height of each subtree */
int lHeight = height(node->left);
int rHeight = height(node->right);
/* use the larger one */
return (lHeight > rHeight) ? (lHeight + 1)
: (rHeight + 1);
}
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
/* Driver code*/
int main()
{
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->right = newNode(8);
root->right->right->left = newNode(6);
root->right->right->right = newNode(7);
/*
Constructed binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
*/
// Function call
printf("Maximum width is %d \n", getMaxWidth(root));
getchar();
return 0;
}
// Java program to calculate width of binary tree
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class Node {
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
/* Function to get the maximum width of a binary tree*/
int getMaxWidth(Node node)
{
int maxWidth = 0;
int width;
int h = height(node);
int i;
/* Get width of each level and compare
the width with maximum width so far */
for (i = 1; i <= h; i++) {
width = getWidth(node, i);
if (width > maxWidth)
maxWidth = width;
}
return maxWidth;
}
/* Get width of a given level */
int getWidth(Node node, int level)
{
if (node == null)
return 0;
if (level == 1)
return 1;
else if (level > 1)
return getWidth(node.left, level - 1)
+ getWidth(node.right, level - 1);
return 0;
}
/* UTILITY FUNCTIONS */
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(Node node)
{
if (node == null)
return 0;
else {
/* compute the height of each subtree */
int lHeight = height(node.left);
int rHeight = height(node.right);
/* use the larger one */
return (lHeight > rHeight) ? (lHeight + 1)
: (rHeight + 1);
}
}
/* Driver code */
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
/*
Constructed binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
*/
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(8);
tree.root.right.right.left = new Node(6);
tree.root.right.right.right = new Node(7);
// Function call
System.out.println("Maximum width is "
+ tree.getMaxWidth(tree.root));
}
}
// This code has been contributed by Mayank Jaiswal
# Python program to find the maximum width of
# binary tree using Level Order Traversal.
# A binary tree node
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Function to get the maximum width of a binary tree
def getMaxWidth(root):
maxWidth = 0
h = height(root)
# Get width of each level and compare the
# width with maximum width so far
for i in range(1, h+1):
width = getWidth(root, i)
if (width > maxWidth):
maxWidth = width
return maxWidth
# Get width of a given level
def getWidth(root, level):
if root is None:
return 0
if level == 1:
return 1
elif level > 1:
return (getWidth(root.left, level-1) +
getWidth(root.right, level-1))
# UTILITY FUNCTIONS
# Compute the "height" of a tree -- the number of
# nodes along the longest path from the root node
# down to the farthest leaf node.
def height(node):
if node is None:
return 0
else:
# compute the height of each subtree
lHeight = height(node.left)
rHeight = height(node.right)
# use the larger one
return (lHeight+1) if (lHeight > rHeight) else (rHeight+1)
# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(8)
root.right.right.left = Node(6)
root.right.right.right = Node(7)
"""
Constructed binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
"""
# Function call
print ("Maximum width is %d" % (getMaxWidth(root)))
# This code is contributed by Naveen Aili
// C# program to calculate width of binary tree
using System;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
public class Node {
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class BinaryTree {
public Node root;
/* Function to get the maximum width of a binary tree*/
public virtual int getMaxWidth(Node node)
{
int maxWidth = 0;
int width;
int h = height(node);
int i;
/* Get width of each level and compare
the width with maximum width so far */
for (i = 1; i <= h; i++) {
width = getWidth(node, i);
if (width > maxWidth) {
maxWidth = width;
}
}
return maxWidth;
}
/* Get width of a given level */
public virtual int getWidth(Node node, int level)
{
if (node == null) {
return 0;
}
if (level == 1) {
return 1;
}
else if (level > 1) {
return getWidth(node.left, level - 1)
+ getWidth(node.right, level - 1);
}
return 0;
}
/* UTILITY FUNCTIONS */
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
public virtual int height(Node node)
{
if (node == null) {
return 0;
}
else {
/* compute the height of each subtree */
int lHeight = height(node.left);
int rHeight = height(node.right);
/* use the larger one */
return (lHeight > rHeight) ? (lHeight + 1)
: (rHeight + 1);
}
}
/* Driver code */
public static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
/*
Constructed binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
*/
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(8);
tree.root.right.right.left = new Node(6);
tree.root.right.right.right = new Node(7);
// Function call
Console.WriteLine("Maximum width is "
+ tree.getMaxWidth(tree.root));
}
}
// This code is contributed by Shrikant13
<script>
// JavaScript program to calculate width of binary tree
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class Node {
constructor(val) {
this.data = val;
this.left = null;
this.right = null;
}
}
var root;
/* Function to get the maximum width of a binary tree*/
function getMaxWidth(node)
{
var maxWidth = 0;
var width;
var h = height(node);
var i;
/* Get width of each level and compare
the width with maximum width so far */
for (i = 1; i <= h; i++) {
width = getWidth(node, i);
if (width > maxWidth)
maxWidth = width;
}
return maxWidth;
}
/* Get width of a given level */
function getWidth(node , level)
{
if (node == null)
return 0;
if (level == 1)
return 1;
else if (level > 1)
return getWidth(node.left, level - 1)
+ getWidth(node.right, level - 1);
return 0;
}
/* UTILITY FUNCTIONS */
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
function height(node)
{
if (node == null)
return 0;
else {
/* compute the height of each subtree */
var lHeight = height(node.left);
var rHeight = height(node.right);
/* use the larger one */
return (lHeight > rHeight) ? (lHeight + 1)
: (rHeight + 1);
}
}
/* Driver code */
/*
Constructed binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
*/
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(8);
root.right.right.left = new Node(6);
root.right.right.right = new Node(7);
// Function call
document.write("Maximum width is "
+ getMaxWidth(root));
// This code is contributed by todaysgaurav
</script>
Output
Maximum width is 3
Time Complexity: O(N2) in the worst case.
Auxiliary Space: O(1)
We can use Queue-based level order traversal to optimize the time complexity of this method. The Queue-based level order traversal will take O(N) time in the worst case. Thanks to Nitish, DivyaC, and tech.login.id2 for suggesting this optimization.
Level Order Traversal using Queue
When a queue is used, we can count all the nodes in a level in constant time. This reduces the complexity to be a linear one.
In this method do the following:
- Store all the child nodes at the current level in the queue.
- Count the total number of nodes after the level order traversal for a particular level is completed.
- Since the queue now contains all the nodes of the next level, we can easily find out the total number of nodes in the next level by finding the size of the queue.
- Follow the same procedure for the successive levels.
- Store and update the maximum number of nodes found at each level.
Below is the implementation of the above approach.
// A queue based C++ program to find maximum width
// of a Binary Tree
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node {
int data;
struct Node* left;
struct Node* right;
Node(int d)
{
this->data = d;
this->left = this->right = NULL;
}
};
// Function to find the maximum width of the tree
// using level order traversal
int maxWidth(struct Node* root)
{
// Base case
if (root == NULL)
return 0;
// Initialize result
int result = 0;
// Do Level order traversal keeping track of number
// of nodes at every level.
queue<Node*> q;
q.push(root);
while (!q.empty()) {
// Get the size of queue when the level order
// traversal for one level finishes
int count = q.size();
// Update the maximum node count value
result = max(count, result);
// Iterate for all the nodes in the queue currently
while (count--) {
// Dequeue an node from queue
Node* temp = q.front();
q.pop();
// Enqueue left and right children of
// dequeued node
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
}
return result;
}
// Driver code
int main()
{
struct Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->right = new Node(8);
root->right->right->left = new Node(6);
root->right->right->right = new Node(7);
/* Constructed Binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7 */
// Function call
cout << "Maximum width is " << maxWidth(root) << endl;
return 0;
}
// This code is contributed by Nikhil Kumar
// Singh(nickzuck_007)
// Java program to calculate maximum width
// of a binary tree using queue
import java.util.LinkedList;
import java.util.Queue;
public class maxwidthusingqueue
{
/* A binary tree node has data, pointer to
left child and a pointer to right child */
static class node
{
int data;
node left, right;
public node(int data) { this.data = data; }
}
// Function to find the maximum width of
// the tree using level order traversal
static int maxwidth(node root)
{
// Base case
if (root == null)
return 0;
// Initialize result
int maxwidth = 0;
// Do Level order traversal keeping
// track of number of nodes at every level
Queue<node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty())
{
// Get the size of queue when the level order
// traversal for one level finishes
int count = q.size();
// Update the maximum node count value
maxwidth = Math.max(maxwidth, count);
// Iterate for all the nodes in
// the queue currently
while (count-- > 0) {
// Dequeue an node from queue
node temp = q.remove();
// Enqueue left and right children
// of dequeued node
if (temp.left != null)
{
q.add(temp.left);
}
if (temp.right != null)
{
q.add(temp.right);
}
}
}
return maxwidth;
}
// Function call
public static void main(String[] args)
{
node root = new node(1);
root.left = new node(2);
root.right = new node(3);
root.left.left = new node(4);
root.left.right = new node(5);
root.right.right = new node(8);
root.right.right.left = new node(6);
root.right.right.right = new node(7);
/* Constructed Binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7 */
// Function call
System.out.println("Maximum width = "
+ maxwidth(root));
}
}
// This code is contributed by Rishabh Mahrsee
# Python program to find the maximum width of binary
# tree using Level Order Traversal with queue.
from _collections import deque
# A binary tree node
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Function to get the maximum width of a binary tree
def getMaxWidth(root):
# base case
if root is None:
return 0
q = deque()
maxWidth = 0
q.append(root)
while q:
# Get the size of queue when the level order
# traversal for one level finishes
count = len(q)
# Update the maximum node count value
maxWidth = max(count, maxWidth)
while (count is not 0):
count = count-1
temp = q.popleft()
if temp.left is not None:
q.append(temp.left)
if temp.right is not None:
q.append(temp.right)
return maxWidth
# Driver program to test above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(8)
root.right.right.left = Node(6)
root.right.right.right = Node(7)
"""
Constructed binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
"""
# Function call
print ("Maximum width is %d" % (getMaxWidth(root)))
# This code is contributed by Naveen Aili
// C# program to calculate maximum width
// of a binary tree using queue
using System;
using System.Collections.Generic;
public class maxwidthusingqueue
{
/* A binary tree node has data, pointer to
left child and a pointer to right child */
public class node
{
public int data;
public node left, right;
public node(int data) { this.data = data; }
}
// Function to find the maximum width of
// the tree using level order traversal
static int maxwidth(node root)
{
// Base case
if (root == null)
return 0;
// Initialize result
int maxwidth = 0;
// Do Level order traversal keeping
// track of number of nodes at every level
Queue<node> q = new Queue<node>();
q.Enqueue(root);
while (q.Count != 0)
{
// Get the size of queue when the level order
// traversal for one level finishes
int count = q.Count;
// Update the maximum node count value
maxwidth = Math.Max(maxwidth, count);
// Iterate for all the nodes in
// the queue currently
while (count-- > 0) {
// Dequeue an node from queue
node temp = q.Dequeue();
// Enqueue left and right children
// of dequeued node
if (temp.left != null)
{
q.Enqueue(temp.left);
}
if (temp.right != null)
{
q.Enqueue(temp.right);
}
}
}
return maxwidth;
}
// Driver code
public static void Main(String[] args)
{
node root = new node(1);
root.left = new node(2);
root.right = new node(3);
root.left.left = new node(4);
root.left.right = new node(5);
root.right.right = new node(8);
root.right.right.left = new node(6);
root.right.right.right = new node(7);
/* Constructed Binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7 */
Console.WriteLine("Maximum width = "
+ maxwidth(root));
}
}
// This code is contributed by Princi Singh
<script>
// JavaScript program to calculate maximum width
// of a binary tree using queue
class node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Function to find the maximum width of
// the tree using level order traversal
function maxwidth(root)
{
// Base case
if (root == null)
return 0;
// Initialize result
let maxwidth = 0;
// Do Level order traversal keeping
// track of number of nodes at every level
let q = [];
q.push(root);
while (q.length > 0)
{
// Get the size of queue when the level order
// traversal for one level finishes
let count = q.length;
// Update the maximum node count value
maxwidth = Math.max(maxwidth, count);
// Iterate for all the nodes in
// the queue currently
while (count-- > 0) {
// Dequeue an node from queue
let temp = q.shift();
// Enqueue left and right children
// of dequeued node
if (temp.left != null)
{
q.push(temp.left);
}
if (temp.right != null)
{
q.push(temp.right);
}
}
}
return maxwidth;
}
let root = new node(1);
root.left = new node(2);
root.right = new node(3);
root.left.left = new node(4);
root.left.right = new node(5);
root.right.right = new node(8);
root.right.right.left = new node(6);
root.right.right.right = new node(7);
/* Constructed Binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7 */
// Function call
document.write("Maximum width is "
+ maxwidth(root));
</script>
Output
Maximum width is 3
Time Complexity: O(N) where N is the total number of nodes in the tree. Every node of the tree is processed once and hence the complexity is O(N).
Auxiliary Space: O(w) where w is the maximum width of the tree.
Maximum width of a Binary Tree
Given a binary tree, the task is to find the maximum width of the given tree. The width of a tree is the maximum of the widths of all levels. Before solving the problem first, let us understand what we have to do. Binary trees are one of the most common types of trees in computer science. They are also called “balanced” trees because all of their nodes have an equal number of children. In this case, we will focus on finding the maximum value of W, which is the width of a binary tree. For example, given a binary tree with root node A, which has two children B and C, where B has two children D and E and C has one child F, the maximum width is 3.
The maximum width of a binary tree is the number of nodes at any level. In other words, it is the minimum number of nodes in a tree that can be traversed before you need to make a choice on which node to visit next.
Example:
Input:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
Output: 3
Explanation: For the above tree,
width of level 1 is 1,
width of level 2 is 2,
width of level 3 is 3
width of level 4 is 2.
So the maximum width of the tree is 3.