FastPrep
Problem · Tree

Count Balanced Nodes in a Rooted Tree

Learn this problem
● MediumDRW logoDRWNEW GRADOA

Problem statement

You are given a rooted tree represented by an adjacency list subtrees. Node 0 is the root, and subtrees[i] lists the indices of the immediate children of node i.

The size of a subtree is the number of nodes it contains, including the node at its root.

A node is balanced if all of its immediate child subtrees have the same size. A node with zero or one child is balanced.

Return the number of balanced nodes in the tree.

Function

solution(subtrees: int[][]) → int

Examples

Example 1

subtrees = [[1,2],[3,4],[5],[],[],[]]return = 5

Node 0 has child-subtree sizes 3 and 2, so it is not balanced. Every other node is balanced, giving a total of 5.

Example 2

subtrees = [[1,2,3],[],[],[]]return = 4

The root has three child subtrees of size 1. The root and all three leaves are balanced.

Example 3

subtrees = [[1,2],[3],[5,6],[4],[],[],[]]return = 7

The two subtrees below the root both have size 3, even though their shapes differ. Every node is balanced.

Constraints

  • subtrees is non-empty and contains one row for every node.
  • Node 0 is the root.
  • Every child index is a valid index into subtrees.
  • Every node other than node 0 appears exactly once among the child lists, node 0 never appears as a child, and the representation contains no cycle.
  • The order of indices within a child list does not affect the result.

More DRW problems

drafts saved locally
public int solution(int[][] subtrees) {
    // Write your code here.
}
subtrees[[1,2],[3,4],[5],[],[],[]]
expected5
checking account