Java program to find maximum width of a binary tree

In this program, we need to find out the maximum width of the binary tree. The width of the binary tree is the number of nodes present in any level. So, the level which has the maximum number of nodes will be the maximum width of the binary tree. To solve this problem, traverse the tree level-wise and count the nodes in each level.

In the given binary tree,

Level 1 has one node, so maxWidth = 1.
Level 2 has two nodes, so maxWidth = 2 as (2 > 1).
Level 3 has four nodes, so maxWidth = 4 as (4 > 2).
Level 4 has one node, so maxWidth = 4 as (1 < 4).

So, the maximum width of the above binary tree is 4 denoted by white ellipse.

Algorithm

• Define Node class which has three attributes namely: data left and right. Here, left represents the left child of the node and right represents the right child of the node.
• When a node is created, data will pass to data attribute of the node and both left and right will be set to null.
• Define another class which has an attribute root.
  • Root represents the root node of the tree and initializes it to null.

a. findMaximumWidth() will find out the maximum width of the given binary tree:

• Variable maxWidth will store the maximum number of nodes present in any level.
• The queue is used for traversing binary tree level-wise.
• It checks whether the root is null, which means the tree is empty.
• If not, add the root node to queue. Variable nodesInLevel keeps track of the number of nodes in each level.
• If nodesInLevel > 0, remove the node from the front of the queue and add its left and right child to the queue. For the first iteration, node 1 will be removed and its children nodes 2 and 3 will be added to the queue. In the second iteration, node 2 will be removed, its children 4 and 5 will be added to the queue and so on.
• MaxWidth will store max(maxWidth, nodesInLevel). So, at any given point of time, it will represent the maximum number of nodes.
• This will continue till all the levels of the tree is traversed.

Program:

Output:

Maximum width of the binary tree: 4