Find the maximum width of binary tree

Introduction

Given a Binary tree, how will you find the maximum width of Binary Tree?

For example, for this Binary tree it has maximum width is 4.

Solution

We can use level order traversal along with queue to find maximum width.
Create an empty queue and start from root node.
Loop while queue is not empty.
- Update maxWidth if count of nodes in queue is greater.
- Remove all current level nodes from queue.
- Add all next level nodes into the queue.

Algorithm - To find the maximum width of binary tree

class Algorithm {

    /**
     * We can use level order traversal along with queue to find maximum width.
     *
     * @param tree binary tree
     * @return maximum width of binary tree
     */
    public int maxWidth(BinaryTree tree) {
        Queue<Node> nodes = new LinkedList<>();
        int maxWidth = 0;
        nodes.add(tree.getRoot());
        while (!nodes.isEmpty()) {
            int count = nodes.size();
            maxWidth = Math.max(maxWidth, count);
            while (count-- > 0) {
                Node node = nodes.remove();
                if (node.getLeft() != null) {
                    nodes.add(node.getLeft());
                }
                if (node.getRight() != null) {
                    nodes.add(node.getRight());
                }
            }
        }
        return maxWidth;
    }
}

Test Scenario

public class AlgorithmTest {

    @Test
    public void canEvaluateMaxWidthOfBinaryTree1() {
        BinaryTree tree = new BinaryTree(new Node(5));
        tree.insert(new Node(4));
        tree.insert(new Node(9));
        tree.insert(new Node(3));
        tree.insert(new Node(7));
        Node node = new Node(8);
        node.setLeft(new Node(5));
        tree.insert(node);
        tree.insert(new Node(6));
        tree.insert(new Node(5));
        assertEquals(4, new Algorithm().maxWidth(tree));
    }

    @Test
    public void canEvaluateMaxWidthOfBinaryTree2() {
        BinaryTree tree = new BinaryTree(new Node(1));
        tree.insert(new Node(2));
        tree.insert(new Node(3));
        tree.insert(new Node(4));
        tree.insert(new Node(5));
        tree.insert(new Node(6));
        tree.insert(new Node(7));
        tree.insert(new Node(8));
        tree.insert(new Node(9));
        tree.insert(new Node(10));
        tree.insert(new Node(11));
        tree.insert(new Node(12));
        tree.insert(new Node(13));
        tree.insert(new Node(14));
        tree.insert(new Node(15));
        assertEquals(8, new Algorithm().maxWidth(tree));
    }
    
}