Largest balanced subtree

Write codeMedium30 min

Your task

Given a binary tree encoded as a level-order array (None marks a missing child), determine the largest number of nodes contained in any subtree that is height-balanced in the AVL sense, where 'height-balanced' means that for every node in that subtree the heights of its left and right children differ by at most 1. Compute it bottom-up in a single post-order pass: each node reports its height, whether its subtree is balanced, and its node count, so a parent can combine children in O(1). Return the size of the largest balanced subtree.

Examples

largest_balanced_subtree(level: list) -> int
Example 1
Inputlargest_balanced_subtree([1, 2, 2, 3, 3, None, None, 4, 4])
Output5