Maximum Width of Binary Tree solution and explanation

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
        queue = deque([(root, 0)])
        max_width = 0
        while queue:
            level_length = len(queue)
            _, first_pos = queue[0]
            for i in range(level_length):
                node, pos = queue.popleft()
                if node.left:
                    queue.append((node.left, 2 * pos))
                if node.right:
                    queue.append((node.right, 2 * pos + 1))
            _, last_pos = queue[-1] if queue else (None, 0)
            max_width = max(max_width, last_pos - first_pos + 1)
        return max_width

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        Deque<Pair<TreeNode, Integer>> queue = new ArrayDeque<>();
        queue.add(new Pair<>(root, 0));
        int maxWidth = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            int firstPos = queue.getFirst().getValue();
            int lastPos = firstPos;  // initialize to avoid lastPos not being set
            for (int i = 0; i < size; i++) {
                Pair<TreeNode, Integer> pair = queue.poll();
                TreeNode node = pair.getKey();
                int pos = pair.getValue();
                if (node.left != null) {
                    queue.add(new Pair<>(node.left, 2 * pos));
                }
                if (node.right != null) {
                    queue.add(new Pair<>(node.right, 2 * pos + 1));
                }
                lastPos = pos;
            }
            maxWidth = Math.max(maxWidth, lastPos - firstPos + 1);
        }
        return maxWidth;
    }
}

class Pair<K, V> {
    private final K key;
    private final V value;
    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }
    public K getKey() { return key; }
    public V getValue() { return value; }
}

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        def dfs(node, depth, position, first_pos_map):
            nonlocal max_width
            if node is None:
                return
            if depth not in first_pos_map:
                first_pos_map[depth] = position
            max_width = max(max_width, position - first_pos_map[depth] + 1)
            dfs(node.left, depth + 1, 2 * position, first_pos_map)
            dfs(node.right, depth + 1, 2 * position + 1, first_pos_map)

        max_width = 0
        first_pos_map = {}
        dfs(root, 0, 0, first_pos_map)
        return max_width

#include <unordered_map>
#include <algorithm>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        unsigned long long maxWidth = 0;
        std::unordered_map<int, unsigned long long> firstPosMap;
        dfs(root, 0, 0, firstPosMap, maxWidth);
        return maxWidth;
    }

private:
    void dfs(TreeNode* node, int depth, unsigned long long position, 
             std::unordered_map<int, unsigned long long>& firstPosMap, unsigned long long& maxWidth) {
        if (!node) return;
        if (!firstPosMap.count(depth)) {
            firstPosMap[depth] = position;
        }
        maxWidth = std::max(maxWidth, position - firstPosMap[depth] + 1);
        dfs(node->left, depth + 1, 2 * position, firstPosMap, maxWidth);
        dfs(node->right, depth + 1, 2 * position + 1, firstPosMap, maxWidth);
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func widthOfBinaryTree(root *TreeNode) int {
	q := []pair{{root, 1}}
	ans := 0
	for len(q) > 0 {
		ans = max(ans, q[len(q)-1].i-q[0].i+1)
		for n := len(q); n > 0; n-- {
			p := q[0]
			q = q[1:]
			root = p.node
			if root.Left != nil {
				q = append(q, pair{root.Left, p.i << 1})
			}
			if root.Right != nil {
				q = append(q, pair{root.Right, p.i<<1 | 1})
			}
		}
	}
	return ans
}

type pair struct {
	node *TreeNode
	i    int
}