Grokking Tree Coding Patterns for Interviews

0% completed

​

Maximum Width of Binary Tree (medium)

Problem Statement

Examples

Try it yourself

Problem Statement

Given the root of a binary tree, find the maximum width of the tree.

The maximum width is the widest level in the tree.

The width of a level is the number of nodes between 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.

You can assume that the result will fit within a 32-bit signed integer.

Examples

Example 1

  • Input: root = [1, 2, 3, 4, null, null, 5]
Image
  • Output: 4
  • Justification: The maximum width is at the last level between nodes 4 and 5. It counts four positions: [4, null, null, 5].

Example 2

  • Input: root = [1, 2, 3, 4, null, 5, 6, null, 7]
Image
  • Output: 4
  • Justification: The maximum width is between nodes 4 and 6 at level 3, counting four positions: [4, null, 5, 6].

Example 3

  • Input: root = [1, 2, null, 3, 4, null, null, 5]
Image
  • Output: 2
  • Justification: The maximum width is at the third level, between nodes 3 and 4. It counts two positions: [3, 4].

Constraints:

  • The number of nodes in the tree is in the range [1, 3000].
  • -100 <= Node.val <= 100

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
Mark as Completed
The Whiz

The Whiz

· 2 years ago

Case 1: Including Null Nodes

public int widthOfBinaryTree (TreeNode root)
{
    if (root == null)
        return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int max = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        // Check if all nodes at this level are null
        boolean allNull = queue.stream().allMatch(Objects::isNull);
        // Calculate level size
        int levelSize = getLevelSize(queue);
        max = Math.max(max, levelSize);
        // Process nodes at the current level
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node != null) {
                queue.offer(node.left);
                queue.offer(node.right);
            }
            else if (!allNu
S

singhursefamily

· a year ago

The input is [1,2,3,4,5,null,7,8,null,null,null,9,10].

I calculate the levels as:

[1]

[2, 3]

[4, 5, null, 7]

[8, null, null, null, 9, 10].

Wouldn't the widest level be the last one, which has a width of 6?

The problem solution says 8, however.

Show 1 reply

On This Page

Problem Statement

Examples

Try it yourself