Find maximum width of a Binary Tree

In this article, we will modify the level order tree traversal algorithm to find the maximum width of a binary tree. In the previous post on balanced binary trees, we have formulated and implemented an algorithm to find the height of a binary tree. We have also implemented an algorithm for level order binary tree traversal in Python.

What is the width of a binary tree?

In a binary tree, a maximum of 2^L  number of nodes can be present at any level L. But, It is very unlikely that each level will have 2^L  number of elements. There may be a lesser number of elements at any level due to the absence of nodes. 

For example, The maximum width of the binary tree given in the following figure is 4 as there are a maximum of four nodes at a single level.

How to find the maximum width of a binary tree?

We will use a modification of the level order tree traversal algorithm to find the maximum width of a binary tree. The idea is to somehow count the number of elements at each level to find their maximum.

For this, we can use a placeholder to separate the elements at different levels in the tree. In the queue used in the level order traversal, we will insert a placeholder after inserting every element of a level. In this way, whenever the placeholder is encountered, we will know that one level of the tree has been traversed and hence the width can be updated.

Algorithm to find the maximum width of a binary tree

We will insert the root node in the queue. After that, we will insert a None object as a placeholder. Whenever a placeholder will be encountered in the queue, the width of the tree will be updated and the None object will be pushed into the queue. 

The algorithm to find the width of the binary tree can be formulated as follows. The algorithm takes the root of the binary tree as input and returns the maximum width.

1. If the root is empty, return 0.
2. Initialize a maximum_width variable to -1.
3. Initialize the current_width variable to 0.
4. Let Q be a queue.
5. Insert root into the Q.
6. Insert None into the queue.
7. Take out a node from Q.
8. If node is None, go to 9. Else go to 11.
9. Compare maximum_width and current_width. Assign maximum of both to maximum_width.
10. Set current_width to 0. If Q is empty or First element of Q is None, Go to 14.
11. Increment current_width by 1.
12. Insert left child of the node into Q.
13. Insert the right child of the node into Q.
14. Check if Q is empty. If Q is not empty, go to 7 else Stop.

Implementation of the algorithm in Python

As we have discussed the general idea and understood the algorithm, Let us look at its implementation in Python. Here we have created a binary tree given in the above image and have calculated the maximum  width of the binary tree.

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None


def insert(root, newValue):
    # if binary search tree is empty, make a new node and declare it as root
    if root is None:
        root = BinaryTreeNode(newValue)
        return root
    # binary search tree is not empty, so we will insert it into the tree
    # if newValue is less than value of data in root, add it to left subtree and proceed recursively
    if newValue < root.data:
        root.leftChild = insert(root.leftChild, newValue)
    else:
        # if newValue is greater than value of data in root, add it to right subtree and proceed recursively
        root.rightChild = insert(root.rightChild, newValue)
    return root


def width(root):
    if root is None:
        return 0
    max_width = -1
    current_width = 0
    Q = [root, None]
    while Q:
        node = Q.pop(0)
        if node is None:
            if max_width < current_width:
                max_width = current_width
            current_width = 0
            if not Q or Q[0] is None:
                continue
            Q.append(None)
        else:
            current_width = current_width + 1
            Q.append(node.leftChild)
            Q.append(node.rightChild)
    return max_width


root = insert(None, 15)
insert(root, 10)
insert(root, 25)
insert(root, 6)
insert(root, 14)
insert(root, 20)
insert(root, 60)
print("Printing the maximum width of the binary tree.")
print(width(root))

Output:

Printing the maximum width of the binary tree.
4

Conclusion

In this article, we have discussed the algorithm to find the maximum width of a binary tree. Stay tuned for more articles on the implementation of different algorithms in Python.