Maximum Width of Binary Tree - Leetcode 662 - Python

Solving Maximum Width of Binary Tree - Leetcode 662, today's daily leetcode problem on April 19th.

0:00 - Read the problem
0:30 - Drawing Explanation
6:33 - Coding Explanation

leetcode 662

#neetcode #leetcode #python

[abhimanyuambastha]

Can do this without using a level counter in the queue. Just use the normal iterative bfs where if there is q.len > 0, then run a for loop to pop all. This way we know they are in the same level, and we can easily identify the leftmost and rightmost numbered node.

[ADITYA-fkzy]

Java version:

class Solution {
public int widthOfBinaryTree(TreeNode root) {

Queue<Triplet> q = new LinkedList<>();

q.offer(new Triplet(root, 1, 0));

int prevLevel = 0, firstInRow = 1;

int res = 0;

while(!q.isEmpty())
{
Triplet t = q.poll();

TreeNode node = t.node;
int i = t.index;
int level = t.level;

if(level > prevLevel)
{
prevLevel = level;
firstInRow = i;
}

res = Math.max(res, i - firstInRow + 1);

if(node.left != null)
{
q.offer(new Triplet(node.left, 2 * i, level + 1));
}

if(node.right != null)
{
q.offer(new Triplet(node.right, 2 * i + 1, level + 1));
}


}

return res;


}
}

class Triplet
{
TreeNode node;
int index;
int level;

Triplet(TreeNode node, int index, int level)
{
this.node = node;
this.index = index;
this.level = level;

}
}

[yefetene]

ans = 1
q = deque()
q.append((root, 1))

while q:
for i in range(len(q)):
cur, l = q.popleft()
if cur.left:
q.append((cur.left, 2*l))
if cur.right:
q.append((cur.right, 2*l + 1))
if len(q) > 1:
ans = max(ans, q[-1][1] - q[0][1] + 1)
return ans

[m.kamalali]

i have Same idea but little diffrent implementation

def bfs(node):
q=deque()
q.append([node, 0])
width=1
while q :
width=max(width, q[-1][1]-q[0][1]+1)
for _ in range(len(q)):
n, p=q.popleft()
if n.left:
q.append([n.left, 2*p+1])
if n.right:
q.append([n.right, 2*p+2])
return width

return bfs(root)

[brandondavison]

This makes more sense to me - level order but use level size to keep track of the level you're on.

def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
queue = deque([(root, 1, 0)])
res = 0

while len(queue) != 0:
levelSize = len(queue)
start = end = 0

for i in range(levelSize):
node, val, level = queue.popleft()
if (node.left):
queue.append((node.left, val * 2, level + 1))
if (node.right):
queue.append((node.right, (val * 2) + 1, level + 1))

if i == 0:
start = val
elif i == levelSize - 1:
end = val

res = max(end - start, res)

return res + 1

[steeve]

My initial thought was to dfs to the deepest node where the max width would be 2^n and tracking leftmost/rightmost where a right child on a left node reduces width by one and vice versa. I wouldn't have come up with assigning the values.
ie. if root.left.left & root.right.right; width =4. If root.right.right were null, but root.right.left, then width would be 3.

[ancai]

At the time of trying this issue(12/18/2023: )
The test case failed with overflow (C++), so I made some code changes:
The core idea is for each level, we don't need to know the absolute number, we only need the relative number starting from left most node.
For eg, the leftmost node will always start from 1, when we start a new level, we record the leftmost num, and use (cur.val - leftmost) * 2 + 1 as the next level left value and (cur.val - leftmost) * 2 + 2 as next level right val. Here is the code:

int widthOfBinaryTree(TreeNode* root) {
Node r(root, 1, 0); // root, level, num;
std::queue<Node> q;
q.push(r);
int prevLevel = 1;
long leftmost = 0;
long res = 0;
while (!q.empty()) {
Node cur = q.front();
q.pop();

// reaches new level, an alternative would be using for loop, i = 0 as first, i = q.size() - 1 as last.
if (cur.level != prevLevel) {
prevLevel = cur.level;
leftmost = cur.num;
}

res = max(res, cur.num - leftmost + 1);

if (cur.root->left) {
q.push({cur.root->left, cur.level + 1, (cur.num - leftmost) * 2 + 1});
}

if (cur.root->right) {
q.push({cur.root->right, cur.level + 1, (cur.num - leftmost) * 2 + 2});
}
}

return res;

}

[palashaa]

Good unique solution, but probably unnecessarily complicated given that you've solved plenty of BFS problems before this one and could use a similar level order traversal approach as you've used in the past. You can just use q size in a for loop to tell when nodes in a q are in the same level and find the left and right most node while popping

[sitronco]

Love yours videos. I was thinking that another way to fix the bug will be to set prevLevel=-1 in that way we always update the level on the first iteration.

[jamesisaacson]

def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
que = deque([(root, 0)])
result = 1

while que:
new_que = deque([])
for entry in que:
node, index = entry
if not node:
continue
new_que.append((node.left, 2 * index))
new_que.append((node.right, 2 * index + 1))
que = new_que
if que:
temp = que[-1][1] - que[0][1] + 1
result = max(result, temp)

return result//2

[mrityunjay]

Is it really intuitive? Not so much. I wouldn't be able to figure out such during an interview for sure.

[Avarn]

Great solution but here's what I got:

from collections import deque

class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
# Initialize the result and a queue for the tree nodes
res = 0
q = deque([(root, 0, 0)])
level_start = {}

# Loop through the queue
while q:
node, depth, pos = q.popleft()

# Store the position of the leftmost node in each level
if depth not in level_start:
level_start[depth] = pos

# Update the result with the maximum width of the current level
res = max(res, pos - level_start[depth] + 1)

# Add the child nodes to the queue
if node.left:
q.append((node.left, depth + 1, pos * 2))
if node.right:
q.append((node.right, depth + 1, pos * 2 + 1))

return res



I used a dictionary to keep track of each node relative to its level. That way it could avoid any bugs prevalent going forward. All in all, it's similar to your approach but I just added that in due to having an error that wasn't the one in your video.

[HistoryHouse]

cant we do total nodes at max hieght - nodes at last level

[ayobrrr]

dfs version -

def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
dlevelmx={}
dlevelmn={}


def rec(node, x, level):
nonlocal dlevelmx
nonlocal dlevelmn
if node:
if (level not in dlevelmx) or (level in dlevelmx and dlevelmx[level]<x):
dlevelmx[level]=x
if (level not in dlevelmn) or (level in dlevelmn and dlevelmn[level]>x):
dlevelmn[level]=x
rec(node.left, x*2, level+1)
rec(node.right, x*2+1, level+1)

rec(root, 0, 0)
ans=0
for k, v in dlevelmx.items():
x=v
y=dlevelmn[k]
ans=max(ans, x-y)
return ans+1

[alexandersmirnov]

we can store node index into node.val also we do not need to store level number
int m = 0;
var q = new LinkedList<TreeNode>();
root.val = 1;
q.add(root);
while(!q.isEmpty()) {
m = Math.max(m, q.getLast().val - q.getFirst().val + 1);
var level = new LinkedList<TreeNode>();
while (!q.isEmpty()) {
var cur = q.pop();
if (cur.left != null) {
cur.left.val = 2 * cur.val;
level.add(cur.left);
}
if (cur.right != null) {
cur.right.val = 2 * cur.val + 1;
level.add(cur.right);
}
}
q = level;
}

[haoli]

Javascript Version.
if didn't let idx to 0. in javascript it will overflow.


var widthOfBinaryTree = function(root) {
if (!root) return 0;
let que = [[root, 1]];
let max = 0;
while(que.length) {
let levelLength = que.length;
const firstIdx = que[0][1]
const lastIdx = que[levelLength - 1][1]
if ((lastIdx - firstIdx + 1) > max) {
max = (lastIdx - firstIdx + 1);
}

for(let i = 0; i < levelLength; i++) {
let [node, idx] = que.shift();
idx -= firstIdx; // !!! without this. overflow will heapean.
if (node.left) {
que.push([node.left, idx * 2]);
}
if (node.right) {
que.push([node.right, idx * 2 + 1]);
}
}
}

return max;
};

[RiazKhan-be]

Complex . You haven't explained clearly

[GoonCity]

I didn’t look at video (yet), but I’m thinking of just regularly traversing with DFS or BFS, recording depth, and incrementing the value in a hash map with level as key

[carnaldesire]

Thank you for the clear explanation, the others just go straight into the solution instead of explaining why it works.