Bhuwan Upadhyay

Talks all about software engineering

Published on

Find the maximum width of binary tree



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.


  • 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;
        while (!nodes.isEmpty()) {
            int count = nodes.size();
            maxWidth = Math.max(maxWidth, count);
            while (count-- > 0) {
                Node node = nodes.remove();
                if (node.getLeft() != null) {
                if (node.getRight() != null) {
        return maxWidth;

Test Scenario

public class AlgorithmTest {

    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(new Node(6));
        tree.insert(new Node(5));
        assertEquals(4, new Algorithm().maxWidth(tree));

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