PPractick

The problem

A tree renderer needs to know how wide a canvas to allocate, and the width of a level is measured between its leftmost and rightmost nodes, counting the empty positions in between, as if the level belonged to a complete binary tree. Give nodes heap-style positions: root 1, left child 2i, right child 2i + 1. The width of a level is last − first + 1. Positions double with every level, so subtract each level's first position before computing children, which keeps the numbers small.

Example: [1, 3, 2, 5, null, null, 9, 6, null, 7] → 7.

Function signature

int widthOfBinaryTree(TreeNode* root);

Test cases

Input (level order)	Output	Explanation
[1, 3, 2, 5, 3, null, 9]	4	Level 2: 5, 3, _, 9
[1, 3, 2, 5, null, null, 9, 6, null, 7]	7	Level 3: 6, then 5 gaps, then 7
[1, 3, 2, 5]	2
[1]	1
[]	0

(Confirm: gaps between the end nodes of a level count; the answer fits in a 32-bit int, though raw positions can grow like 2^depth.)

How interviewers phrase it

• "Return the maximum width of a binary tree, where the width of a level is the length between the leftmost and rightmost non-null nodes, including nulls in between" (LeetCode 662).

Clarifying questions to ask

1. Do null positions between the end nodes count? (Yes.)
2. Do nulls outside the end nodes count? (No.)
3. How deep can the tree be? (Up to 3000, so raw positions overflow any integer type without normalisation.)

Follow-ups to expect

1. "Why heap indices?"
2. "How do you avoid overflow?"
3. "Why unsigned arithmetic?"
4. "DFS version?"
5. "Complexity?"

Related questions

• Zig Zag or Spiral Traversal Medium
• Vertical Order Traversal Medium
• Top View of BT Medium
• Bottom view of BT Medium
• Right/Left View of Binary Tree Medium
• Level Order Traversal Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in