class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class MaximumWidth {
Node root;
public int getMaxWidth(Node root) {
int maxWidth = 0;
// Get the height of the tree
int height = getHeight(root);
// Calculate the width at each level and take the maximum width
for (int i = 1; i <= height; i++) {
int width = getWidth(root, i);
if (width > maxWidth) {
maxWidth = width;
}
}
return maxWidth;
}
private 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;
}
private int getHeight(Node node) {
if (node == null) {
return 0;
}
int leftHeight = getHeight(node.left);
int rightHeight = getHeight(node.right);
return 1 + Math.max(leftHeight, rightHeight);
}
public static void main(String[] args) {
MaximumWidth tree = new MaximumWidth();
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.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.left.right.left = new Node(8);
tree.root.left.right.right = new Node(9);
tree.root.right.right.left = new Node(10);
int maxWidth = tree.getMaxWidth(tree.root);
System.out.println("Maximum width of binary tree is: " + maxWidth);
}
}