Introduction
Before diving into the problem, let’s first understand the width or breadth of a binary tree. The number of nodes present at the given level can determine the width of a binary tree. To be more specific, the maximum number of nodes at any binary tree level is the maximum width of a binary tree.
The maximum width of a binary tree is the count of nodes without children. It represents the minimum nodes that must be traversed before needing to decide on the next node to visit.
Let’s understand it with some examples:
Example - 1:
Since the maximum number of nodes present at Level-1 is 2, the maximum width of the binary tree is 2
Example-2:
As you can see, the maximum number of nodes present at level 2 is 4; hence the maximum width of the binary tree is 4.
Now that you know how to find the maximum width of a binary tree, we need to build an algorithm that will allow us to return the maximum width for any binary tree.
It is recommended to Implement the stated maximum width in binary tree problem on your own before moving to the solution.
You can obtain a greater understanding of data structures and algorithms by solving on your own the stated maximum width problem in a binary tree. By addressing the problem on your own, you'll have the chance to experiment with different strategies, spot potential challenges, and improve your problem-solving abilities.
Let's discuss the approach to solve the stated problem:
Maximum Width using Level-order Traversal
The naive yet effective approach can be using Level-wise traversal. As we aim to find the maximum number of nodes level-wise thus, employing Level order Traversal (or Breadth-first search) will suffice.
Level-order traversal or breadth-first search starts traversing at the tree from root and explores all nodes at the present level before moving on to the nodes at the next depth level.
Consider the below diagram:
This is how the Level order traversal works in trees or any data structure.
Now let’s understand the algorithm for finding the maximum width of a binary tree using the Level-order traversal.
In the given binary tree:
Level 1 has 1 node, so maxWidth = 1
Level 2 has 2 node, so maxWidth = 2( 2 > 1)
Level 3 has 4 node, so maxWidth = 4( 4 > 2)
Hence, the maximum width will be 4.
Level Order Traversal without queue
Without using a queue, level order traversal in a binary tree involves tracking each level's nodes separately, usually through depth-first or recursion-based approaches. This method typically requires additional bookkeeping and may not be as efficient as using a queue. In this method:
- You would typically use a recursive approach.
- Start by calculating the height of the binary tree. Then, iterate from height 1 to the maximum height.
- At each level, traverse the tree and print the nodes encountered at that level.
- You might need a helper function that takes the root node and the current level as parameters.
- This method involves multiple passes through the tree and might not be as efficient as using a queue.
Level Order Traversal using Queue
Level order traversal using a queue involves iterating through each level of a binary tree horizontally. Starting from the root node, each level's nodes are processed sequentially by enqueueing child nodes and dequeueing parent nodes. This method ensures nodes are visited in a breadth-first manner, making it efficient and easy to implement. In this method:
- Initialize a queue and enqueue the root node.
- Begin a loop that continues until the queue is empty.
- Inside the loop, dequeue a node, process it (print its value, for example), and enqueue its children (if any) from left to right.
- Repeat this process until all nodes are processed.
- This method ensures that nodes are visited level by level, from left to right, which is the characteristic of level order traversal.
- Using a queue helps in keeping track of the nodes to be processed at each level efficiently, ensuring a breadth-first search pattern.
Also read - Boundary Traversal of Binary Tree
Algorithm
-
Define the Node class, which contains three attributes: data, left, and right where, the left child of the node is represented by left, and the right child of the node is represented by right
-
When a node is constructed, data is passed to the node's data attribute, and both left and right are set to null
-
Create a new class with the root attribute. The root represents the tree's root node and sets its value to null
- findMaxWidth() will find out the maximum width of a binary tree
-
The variable maxWidth will keep track of the total number of nodes in each level
-
The queue is used to traverse the binary tree on a level-by-level basis
-
The function also determines if the root is null, indicating that the tree is empty
-
If this is not the case, add the root node to the queue. Variable level_nodes keep track of the number of nodes in each level
- Remove the node from the front of the queue and add its left and right children to the queue if the number of level_nodes > 0
-
In the above diagram, node 1 will be eliminated in the first iteration, and its children nodes 2 and 3 will be added to the queue. Node 2 will be eliminated in the second iteration, and its offspring 4 and 5 will be added to the queue, and so on
-
MaxWidth is a variable that stores the maximum width (maxWidth, level_nodes). As a result, it will always represent the maximum number of nodes at any given time
5. Finally, Print the maxWidth
Now, let’s look at the Implementation:
Implementation in Java
- Java
Java
// Java Implementation to find the maximum width of a binary tree
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTree {
// Represent the node of a binary tree
public static class Node{
/* Node has three components -> data , left and right
data
/ \
left right
*/
int data;
Node left;
Node right;
// Function for assigning the respected values to the components
public Node(int data){
// Assign data to the new node and set its left and right children to null
this.data = data;
this.left = null;
this.right = null;
}
}
//Represent the root of a binary tree
public Node root;
// Constructor for initially assigning the root to null
public BinaryTree(){
root = null;
}
// findMaxWidth() will find out the maximum width of the given binary tree
public int findMaxWidth() {
int maxWidth = 0;
// Variable level_nodes keep note of number of nodes in each level
int level_nodes = 0;
// queue data structure will be used to keep note of the nodes of tree level-wise
Queue<Node> queue = new LinkedList<Node>();
// Check if root is null, then width will be 0
if(root == null) {
// print Tree is empty and return
System.out.println("Tree is empty");
return 0;
}
else {
//Add the root node to queue as it serves the first level
queue.add(root);
// Loop until the queue becomes empty
while(queue.size() != 0) {
//Variable level_nodes will hold the size of queue i.e. number of elements in queue
level_nodes = queue.size();
//maxWidth will hold the maximum width among the level_nodes and maxWidth itself.
maxWidth = Math.max(maxWidth, level_nodes);
/* If variable level_nodes contains more than one node then, for each node, its left and right child will be added to the queue */
while(level_nodes > 0) {
Node curr = queue.remove();
if(curr.left != null)
queue.add(curr.left);
if(curr.right != null)
queue.add(curr.right);
// decrement the level_nodes by one so that it jumps to the remaining size
level_nodes--;
}
}
}
return maxWidth;
}
public static void main(String[] args) {
BinaryTree binaryT = new BinaryTree();
/* Construct the following binary tree
1
/ \
2 3
/ \ / \
4 5 6 7
*/
binaryT.root = new Node(1);
binaryT.root.left = new Node(2);
binaryT.root.right = new Node(3);
binaryT.root.left.left = new Node(4);
binaryT.root.left.right = new Node(5);
binaryT.root.right.left = new Node(6);
binaryT.root.right.right = new Node(7);
// print the maximum width of the given tree
System.out.println("Maximum width of a binary tree: " + binaryT.findMaxWidth());
}
} 
Output
Maximum width of a binary tree: 4
Complexity Analysis
Time Complexity: O(N), where N is the number of nodes present in a binary tree. Since each node is processed once, therefore the time complexity is O(N).
Space Complexity: The Space Complexity is O(W), where W is the maximum width of a binary tree. Because, In level order traversal, a queue is kept whose maximum size at any given time can be as large as the binary tree's maximum width. In the worst case, it can be O(N), where N is the number of nodes present in a binary tree.
Implementation in python
- python
python
# Python Implementation to find the maximum width of a binary tree
# Represent a node of a binary tree
class Node:
def __init__(self,data):
# Assign data to the new node and set its left and right children to None
""" Node has three components -> data , left and right
data
/ \
left right
"""
self.data = data;
self.left = None;
self.right = None;
class BinaryTree:
def __init__(self):
# Represent the root of the binary tree
self.root = None;
# findMaxWidth() will find out the maximum width of a given binary tree
def findMaxWidth(self):
maxWidth = 0;
# Variable Level_nodes keep tracks of the number of nodes in each level
level_nodes = 0;
# queue data structure will be used to keep note of the nodes of tree level-wise
queue = [];
# Check if the root is null, then width will be 0
if(self.root == None):
print("Tree is empty");
return 0;
# If the root isn't empty
else:
# Add the root node to queue as it serves the first level
queue.append(self.root);
# Loop until the queue becomes empty
while(len(queue) != 0):
# Variable level_nodes will hold the size of queue i.e. number of elements in queue
level_nodes = len(queue);
# maxWidth will hold maximum width
maxWidth = max(maxWidth, level_nodes);
# If variable level_nodes contains more than one node
# then, for each node, its left and right child will be added to the queue
while(level_nodes > 0):
curr = queue.pop(0);
if(curr.left != None):
queue.append(curr.left);
if(curr.right != None):
queue.append(curr.right);
# decrement the level_nodes by one so that it jumps to the remaining size
level_nodes = level_nodes - 1;
return maxWidth;
binaryT = BinaryTree();
#Add nodes to the binary tree
""" Construct the following binary tree
1
/ \
2 3
/ \ / \
4 5 6 7
"""
binaryT.root = Node(1);
binaryT.root.left = Node(2);
binaryT.root.right = Node(3);
binaryT.root.left.left = Node(4);
binaryT.root.left.right = Node(5);
binaryT.root.right.left = Node(6);
binaryT.root.right.right = Node(7);
# print the maximum width of given tree
print("Maximum width of a binary tree: " + str(binaryT.findMaxWidth()));
Output
Maximum width of a binary tree: 4
Complexity Analysis
Time Complexity: O(N), where N is the number of nodes present in a binary tree. Since each node is processed once, therefore the time taken will be O(N).
Space Complexity: O(W), where W is the maximum width of a binary tree. Because, In level order traversal, a queue is kept whose maximum size at any given time can be as large as the binary tree's maximum width. In the worst case, it can be O(N), where N is the number of nodes present in a binary tree.
Pictorial Representation of the above example in implementation:-
7+ registered 
