Widest Tree Level

Medium

You get the root of a non-empty binary tree. The width of a level is the number of positions from its leftmost node to its rightmost node inclusive, counting the empty spots in between as well: the places where nodes would be if the tree were complete down to that level. Return the largest width over all levels.

Example 1

root=tree_node([8, 2, 6, None, 4, 5, None]) → 2

Level 2 holds 4 (the right child of 2) and 5 (the left child of 6). Nothing lies between them, so the width is 2.

Example 2

root=tree_node([1, 7, 3, 9, None, None, 2]) → 4

On level 2 the outer nodes are 9 and 2; a complete tree would fit two more nodes between them, so the width is 4.

Example 3

root=tree_node([0]) → 1

Constraints

The tree has between 1 and 3000 nodes
-100 ≤ node value ≤ 100
The answer fits in a signed 32-bit integer

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Breadth-First Search Binary Tree

Similar problems

The Tree Seen From the Right Medium Tree Columns, Top Down Medium First Value on the Lowest Row Medium Largest Value on Each Tree Level Medium Insert a Tree Level Medium

Input

root=tree_node([8, 2, 6, None, 4, 5, None])

Expected

Run checks the first 3 tests in your browser. Submit checks all 98 tests on the server, hidden ones included.