Binary Tree Max Width

Problem

Return the maximum width of a binary tree.

tree is a level-order list with None marking missing nodes. The width of a level is the distance between its leftmost and rightmost nodes counting the missing positions between them, using the array indices as positions.

Return the largest width over all levels (0 for an empty tree).

Hint

Use the heap indices themselves as x-coordinates; the width is last minus first plus one.

Test cases

case 1

in: [[1,3,2,5,3,null,9]]

expected: 4

case 2

in: [[1,3,null,5,3]]

expected: 2

case 3

in: [[1,2,3]]

expected: 2

case 4

in: [[]]

expected: 0

case 5

in: [[1]]

expected: 1

Starter codePython

def max_width(tree):
    # Your code here
    pass

5 test cases · run your code against them in the editor