AlgoExplained.dev

def widthOfBinaryTree(root):
Defines the function `widthOfBinaryTree` which takes the `root` of a binary tree and returns its maximum width as an integer.
    if not root:
Base case: if the tree is empty (root is None), there are no levels so the width is 0.
        return 0
Return 0 immediately for an empty tree since no width exists.
    max_width = 0
Initialize `max_width` to 0. This variable tracks the largest width found across all levels.
    queue = deque([(root, 0, 0)])
Create a deque initialized with a tuple of (root node, depth=0, position=0). Position 0 is the root's index in the virtual complete binary tree array.
    while queue:
Continue processing while there are still nodes in the queue (levels remaining to process).
        level_len = len(queue)
Capture the number of nodes at the current level before processing. This separates one level from the next.
        _, depth, left_pos = queue[0]
Peek at the front of the queue to record the position of the leftmost node at this level (`left_pos`). This is the starting point for width calculation.
        for i in range(level_len):
Loop exactly `level_len` times to process only nodes belonging to the current level. Index `i` helps identify the last node.
            node, d, pos = queue.popleft()
Dequeue the front node along with its depth and position. FIFO order ensures left-to-right processing within each level.
            if i == level_len - 1:
Check if this is the last node in the current level (the rightmost non-null node). Only then do we compute the width for this level.
                current_width = pos - left_pos + 1
Compute the width of this level: rightmost position minus leftmost position plus 1. The +1 accounts for inclusive counting of both endpoints.
                max_width = max(max_width, current_width)
Update `max_width` if the current level's width exceeds the previously recorded maximum.
            if node.left:
Check if the current node has a left child before enqueuing it. Null children are skipped since they don't contribute to width.
                queue.append((node.left, d + 1, pos * 2))
Enqueue the left child with incremented depth and position `pos * 2` (following the complete binary tree array indexing rule).
            if node.right:
Check if the current node has a right child before enqueuing it.
                queue.append((node.right, d + 1, pos * 2 + 1))
Enqueue the right child with incremented depth and position `pos * 2 + 1` (right sibling index in the array representation).
    return max_width
Return the maximum width found across all levels of the tree.

public int widthOfBinaryTree(TreeNode root) {
Defines the method that takes a TreeNode root and returns the maximum width of the tree as an integer.
    if (root == null) return 0;
Base case: if the tree is empty, return 0 immediately since there is no width to measure.
    int maxWidth = 0;
Initialize `maxWidth` to 0. This will hold the largest width encountered across all levels during traversal.
    Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
Create a LinkedList-based Queue storing Pairs of (TreeNode, Integer position). Each entry pairs a node with its positional index.
    queue.offer(new Pair<>(root, 0));
Add the root node with initial position 0 to start the BFS. Position 0 represents the root's index in the virtual complete binary tree.
    while (!queue.isEmpty()) {
Continue processing while there are still nodes in the queue (more levels to visit).
        int levelSize = queue.size();
Record the number of nodes at the current level before processing begins. This is critical for level separation in BFS.
        int leftPos = queue.peek().getValue();
Peek at the front of the queue to get the position of the leftmost node at this level. This anchors the width calculation.
        for (int i = 0; i < levelSize; i++) {
Loop exactly `levelSize` times to process only the nodes that belong to the current level. Use `i` to detect the last node.
            Pair<TreeNode, Integer> pair = queue.poll();
Remove and retrieve the front pair (node, position) from the queue. FIFO ensures left-to-right processing within the level.
            TreeNode node = pair.getKey();
Extract the TreeNode from the pair for accessing its children.
            int pos = pair.getValue();
Extract the position value from the pair. This is used for width calculation and computing child positions.
            if (i == levelSize - 1) {
Check if this is the last node in the current level (rightmost non-null node). We only compute width once per level, at the end.
                maxWidth = Math.max(maxWidth, pos - leftPos + 1);
Compute width as `pos - leftPos + 1` and update `maxWidth` if this level's width is larger than any seen before.
            }
End of the conditional block for width computation on the last node of the level.
            if (node.left != null) queue.offer(new Pair<>(node.left, pos * 2));
If the left child exists, enqueue it with position `pos * 2`. This follows the heap-style indexing where left child is at 2*i.
            if (node.right != null) queue.offer(new Pair<>(node.right, pos * 2 + 1));
If the right child exists, enqueue it with position `pos * 2 + 1`. Right child is at 2*i+1 in the array representation.
        }
End of the for loop that processes all nodes at the current level.
    }
End of the while loop. All levels have been processed.
    return maxWidth;
Return the maximum width found across all levels of the binary tree.
}
End of the method.

int widthOfBinaryTree(TreeNode* root) {
Defines the function that takes a pointer to the root TreeNode and returns the maximum width as an integer.
    if (!root) return 0;
Base case: if the tree is empty (null pointer), return 0 immediately since no width can be measured.
    int maxWidth = 0;
Initialize `maxWidth` to 0. This variable keeps track of the widest level encountered during BFS traversal.
    queue<pair<TreeNode*, long>> q;
Create a queue storing pairs of (TreeNode pointer, long position). Using `long` prevents integer overflow for deep trees where positions grow exponentially.
    q.push({root, 0});
Push the root node with initial position 0 onto the queue to begin BFS traversal.
    while (!q.empty()) {
Continue processing while there are still entries in the queue (levels remain unprocessed).
        int levelSize = q.size();
Get the number of nodes at the current level. This must be captured before the loop modifies the queue.
        long leftPos = q.front().second;
Read the position of the leftmost node at this level (front of queue). Stored as `long` to match the position type.
        for (int i = 0; i < levelSize; i++) {
Iterate exactly `levelSize` times to process only nodes belonging to the current level. Index `i` identifies the last node.
            auto [node, pos] = q.front();
Use structured binding to extract the node pointer and position from the front of the queue without removing it yet.
            q.pop();
Remove the front element from the queue. In C++, `front()` peeks and `pop()` removes — they are separate operations.
            if (i == levelSize - 1) {
Check if this is the last node processed at the current level (the rightmost non-null node). Width is computed here.
                maxWidth = max(maxWidth, (int)(pos - leftPos + 1));
Compute the current level's width as `pos - leftPos + 1`, cast to int, and update `maxWidth` if larger. The +1 makes the range inclusive.
            }
End of the conditional block for width computation at the end of each level.
            if (node->left) q.push({node->left, pos * 2});
If the left child exists, push it onto the queue with position `pos * 2` following the complete binary tree indexing scheme.
            if (node->right) q.push({node->right, pos * 2 + 1});
If the right child exists, push it onto the queue with position `pos * 2 + 1` (right sibling index in array representation).
        }
End of the for loop that processes all nodes at the current level.
    }
End of the while loop. All levels have been traversed.
    return maxWidth;
Return the maximum width found across all levels of the binary tree.
}
End of the function.