Report Tree Levels and Balanced Subtrees

Problem Statement

You are given a binary tree represented as a zero-based array values, following standard heap layout:

• The root is at index 0.
• For any node at index i, its left child is at index 2 * i + 1 and its right child is at index 2 * i + 2.
• An element in values can be None, indicating the absence of a node at that position. An index i >= len(values) also represents an absent node.

A subtree rooted at node u is considered height-balanced if:

1. The left subtree is height-balanced (an empty subtree is trivially balanced with height 0).
2. The right subtree is height-balanced.
3. The absolute difference between the height of the left subtree and the height of the right subtree is at most 1.

The height of an empty subtree is 0, and the height of a non-empty subtree is 1 + max(left_height, right_height).

Implement describe_balanced_nodes(values) to find all existing nodes whose subtrees are height-balanced. For each such node, return its index in the array and its 0-indexed level (where the root at index 0 has level 0).

Return the results as a list of tuples (index, level) sorted primarily by level in ascending order, and secondarily by index in ascending order.

Function Signature

def describe_balanced_nodes(values: list[int | None]) -> list[tuple[int, int]]:
    pass

Constraints

• 0 <= len(values) <= 10^5
• values[i] is an integer between -10^9 and 10^9, or None.

Examples

Example 1

Input: values = [1, 2, 3, 4, None, 6, 7]
Output: [(1, 1), (2, 1), (3, 2), (5, 2), (6, 2)]

Explanation:

• Index 0 (value 1, level 0): Left subtree (rooted at 1) has height 2 (children: left=4, right=None). Right subtree (rooted at 2) has height 2 (children: left=6, right=7). Height difference is |2 - 2| = 0. However, the left child at index 1 is checked: left child has left subtree of height 1 (node 4) and right subtree of height 0 (None), which has height difference |1 - 0| = 1 (balanced). Node 1 is balanced. Right child at index 2 has left subtree height 1 and right subtree height 1 (balanced). Since both subtrees are balanced and heights differ by 0, index 0 is also balanced! Wait: if index 0 is balanced, shouldn't index 0 be included? Yes! Let's check: Node 0 is balanced, so it should be included as (0, 0). Let's provide the exact example where node 0 is NOT balanced to illustrate unbalanced cases clearly:

Input: values = [1, 2, None, 3]
Output: [(1, 1), (3, 2)]

Explanation:

• Node 0 has left child 1 (height 2) and right child None (height 0). The difference is |2 - 0| = 2 > 1, so node 0 is not balanced.
• Node 1 has left child 3 (height 1) and right child None (height 0). The difference is |1 - 0| = 1 <= 1, and both subtrees are balanced, so node 1 is balanced (level 1).
• Node 3 has no children (height 1), so it is balanced (level 2).

Example 2

Input: values = []
Output: []