Java program to find maximum width of a binary tree

In the following example of Java program to find the maximum width of a binary tree :

Program :

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);
    }
}

Output :

Maximum width of binary tree is: 4

In this program, we first create a binary tree with some nodes. We define a function getMaxWidth() that takes in the root node of the binary tree as an input argument and returns the maximum width of the binary tree.

The getMaxWidth() function calls two helper functions, getWidth() and getHeight(), to calculate the width and height of the binary tree respectively. The getWidth() function calculates the width of the binary tree at a given level, and the getHeight() function calculates the height of the binary tree.

Finally, the getMaxWidth() function calculates the width at each level of the binary tree and returns the maximum width. We call the getMaxWidth() function with the root node of the binary tree and print out the maximum width of the binary tree.