Report Tree Levels and Balanced Subtrees

Quick Overview

Implement `describe_balanced_nodes(values)` for a binary tree represented as a zero-based heap array. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.

Report Tree Levels and Balanced Subtrees

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement `describe_balanced_nodes(values)` for a binary tree represented as a zero-based heap array. For an existing node at index `i`, its children are at `2*i + 1` and `2*i + 2`. A `null` slot means no node; a valid input never places an existing node below a missing parent. A node's subtree is height-balanced when both child subtrees are height-balanced and their heights differ by at most one. The empty subtree has height `0` and a leaf has height `1`. Return one integer record `[index, level, balanced_flag]` for every existing node, ordered by increasing array index. The root is at level `0`. Encode a balanced subtree as `1` and an unbalanced subtree as `0`, so the return type is a portable list of integer lists. ### Constraints - `0 <= len(values) <= 200000` - Every non-null value is an integer in `[-10^9, 10^9]`. - Values need not be unique; use the array index as node identity. - An empty input returns an empty list. ```hint Stress irregular shapes Test a one-sided chain, a root with only one child, and missing children at different levels. ``` ```hint Check depth robustness The largest valid input should not fail solely because the tree is deep. ```

Quick Answer: Implement `describe_balanced_nodes(values)` for a binary tree represented as a zero-based heap array. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.

|Home/Coding & Algorithms/Netflix
Netflix logo
Netflix
Aug 11, 2026, 12:00 AM
mediumSoftware EngineerOnsiteCoding & Algorithms
0
0

Implement describe_balanced_nodes(values) for a binary tree represented as a zero-based heap array. For an existing node at index i, its children are at 2*i + 1 and 2*i + 2. A null slot means no node; a valid input never places an existing node below a missing parent.

A node's subtree is height-balanced when both child subtrees are height-balanced and their heights differ by at most one. The empty subtree has height 0 and a leaf has height 1.

Return one integer record [index, level, balanced_flag] for every existing node, ordered by increasing array index. The root is at level 0. Encode a balanced subtree as 1 and an unbalanced subtree as 0, so the return type is a portable list of integer lists.

Constraints

  • 0 <= len(values) <= 200000
  • Every non-null value is an integer in [-10^9, 10^9] .
  • Values need not be unique; use the array index as node identity.
  • An empty input returns an empty list.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...