FastPrep
Problem · Tree

Balanced Tree Node Report

Learn this problem
● MediumNetflix logoNetflixFULLTIMEONSITE INTERVIEW

Problem statement

A binary tree contains n nodes indexed from 0 to n - 1, with node 0 as the root. Arrays values, left, and right describe the tree. A child index of -1 means that child is absent.

A node is balanced when the heights of its left and right subtrees differ by at most one and both child subtrees are balanced. An empty subtree has height 0.

Perform a root-left-right depth-first traversal. Return one row per visited node as [value, level, balanced], where the root has level 0 and balanced is 1 for a balanced subtree or 0 otherwise.

Function

reportBalancedNodes(values: int[], left: int[], right: int[]) → int[][]

Examples

Example 1

values = [10,5,15]left = [1,-1,-1]right = [2,-1,-1]return = [[10,0,1],[5,1,1],[15,1,1]]

Both leaves are balanced, and the root's two subtree heights are equal.

Example 2

values = [1,2,3,4]left = [1,2,3,-1]right = [-1,-1,-1,-1]return = [[1,0,0],[2,1,0],[3,2,1],[4,3,1]]

The bottom two nodes are balanced. Node 2 and then the root have left and right subtree heights differing by more than one.

Example 3

values = [7,7,9,4,6]left = [1,3,-1,-1,-1]right = [2,4,-1,-1,-1]return = [[7,0,1],[7,1,1],[4,2,1],[6,2,1],[9,1,1]]

Traversal order is based on node structure rather than value, so duplicate values are preserved in separate rows.

Constraints

  • 1 <= values.length == left.length == right.length <= 2 * 10^5
  • -10^9 <= values[i] <= 10^9
  • Each child entry is -1 or a valid node index.
  • The child arrays describe one rooted binary tree: every non-root node has exactly one parent, and every node is reachable from node 0.
  • The tree height is at most 2000.

More Netflix problems

drafts saved locally
public int[][] reportBalancedNodes(int[] values, int[] left, int[] right) {
  // write your code here
}
values[10,5,15]
left[1,-1,-1]
right[2,-1,-1]
expected[[10,0,1],[5,1,1],[15,1,1]]
checking account