Node value equals average of its children

Problem Given a binary tree, check whether every node's value equals the average of its children's values (clarify with the interviewer: direct children only — the common variant — and integer vs exact average; single-child and leaf conventions).

Input / Output

• Input: tree root. Output: boolean (or count of satisfying nodes per variant).

Constraints

• Up to 10^5 nodes; O(n) single traversal.

Example

• Node 4 with children 3 and 5 → 4 == (3+5)/2 ✓. Node 4 with single child 4 ✓ (average of one child). Leaves: vacuously true (no children).

Expected approach

• Any traversal (DFS): per node with ≥1 child, compare value against sum/count of present children — integer division vs exact rational comparison (use value * count == sum to dodge floats — worth stating). Leaves pass vacuously. O(n)/O(h). The subtree-average variant (node equals average of ENTIRE subtree) upgrades to post-order returning (sum, count) pairs — recognize which is being asked and mention the other.