Maximum Width of a Binary Tree || <The most intuitive solution>

Catchy Thumbnail, haha

Before starting out, I promise you three things: you’ll have a better understanding of the concept of overflow, you’ll get an intuitive idea on Serialization of nodes in a Binary Tree, you’ll get accustomed to a hack.

Without further ado, let’s begin.

Question> Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

It is guaranteed that the answer will in the range of a 32-bit signed integer.

Let’s now understand the question and come up with intuitions for the solution.

idea behind BFS traversal

Intuition 1: We are talking about levels, so we require to traverse the tree in a level order, umm, Breadth First Traversal, here I come.

width = last- first + 1

serialization of nodes

Intuition 2: If we’ll somehow mark the nodes for each level with some incrementing serial numbers/ ids, then we can simply subtract the right most with left most serial number, add 1 and that will give us the width of that level. Serialization of Nodes.

Let’s quickly go through the BFS traversal first,

BFS traversal

Now with BFS traversal we need to serialize each node with serial numbers, we can use the formula, for ‘i’ parent node its two children will be ‘2*i+1’ and ‘2*i+2’, but the problem here is, the tree can be very very very large and that will lead to integer overflow leading to runtime errors. It’s time to get accustomed to a new hack here.

The Hack

let’s take an example of following BT,

         A
       /   \
      B     C
     / \   / \ 
    D   E F   G

Let’s start serialization from node A it’ll be marked with 0 further its children will be marked as 1 and 2 respectively. Now we can mark nodes D, E, F, G with 3, 4, 5, and 6 but if the tree kept on growing it’ll lead to huge numbers. Let’ s analyze, in the Leetcode problem for the same, max tree height can be 3000 if the tree will be skewed then their will be 2^3000 -1 nodes in total this will surpass all the available data types, so we cannot serialize the tree this way.

We’ll serialize the tree using a special hack, let’s understand the hack using the following example.

**to mark the nodes we're using the above discussed formula, left child = 2*(marked value of parent node)+ 1 and right child = 2*(marked value of parent node) + 2

Level 1: We’re marking the root node with 0

Level 2: Node 2 and 3 will be marked 1 and 2 respectively.

Level 3: We’ll subtract 1 from the marked serials of both node 2 and 3, and then will mark their children accordingly.

node 4: 2*(marked value of node 2 — 1) + 1 = 1

node 5: 2*(marked value of node 2 — 1) + 2 = 2

node 6: 2*(marked value of node 3 — 1) + 1 = 3

node 7: 2*(marked value of node 3 — 1) + 2 = 4

level 3:

nodes 8, 9, 10, 11, 12, 13, 14, 15, 16: 1, 2, 3, 4, 5, 6, 7, 8

Great, now after marking is done, let’s simply traverse BFS and find the max width across all the levels.

final code

code accepted on Leetcode

That’s it for today. Bon Adieu.