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

--

*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.*

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.

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,

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.

That’s it for today. Bon Adieu.