Maximum Width of Binary Tree

Problem :

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 are also counted into the length calculation.

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

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

Solution :

Intention is at each level of tree ( BFS- Level Order Traversal) pick the maximum of (right index — Left index)+1, where index = if its a left node 2*Level and if its right node 2*Level+1. In the above case when indexes are applied the Tree would get translated as below

Code snippet :

/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/

public class NodeInfo{
public TreeNode node;
public int pos;
public NodeInfo(TreeNode _node,int _pos){
node=_node;
pos=_pos;
}

public int getPos(){
return pos;
}
public TreeNode getNode(){
return node;
}

}
public class Solution {
public int WidthOfBinaryTree(TreeNode root) {
if(root==null){
return 0;
}
var maxwidth=0;
var linkedlist = new LinkedList<NodeInfo>();
linkedlist.AddLast(new NodeInfo(root,0));
while(linkedlist.Count()>0){
var len=linkedlist.Count();
maxwidth=Math.Max(maxwidth,linkedlist.Last().getPos()-linkedlist.First().getPos()+1);
for(int i=0;i<len;i++){
var element=linkedlist.First();
linkedlist.RemoveFirst();
if(element.getNode().left!=null){

linkedlist.AddLast(new NodeInfo(element.getNode().left,element.getPos()*2));
}
if(element.getNode().right!=null){

linkedlist.AddLast(new NodeInfo(element.getNode().right,element.getPos()*2+1));
}

}

}
return maxwidth;
}
}

Reference :

https://leetcode.com/problems/maximum-width-of-binary-tree/