Trace lab in Binary Trees and Traversals

Mission

Count children for every node in a parent array.

Learning outcome: Trace parent-child relationships

Correctness contract

Invariant: Every non-root node has one parent, and traversal visits every reachable node exactly once.

Required technique: Accumulate one child count for every non-root parent index.

Complexity target: time O(n); space O(n).

Input and output

Input: n followed by n parent indexes, using -1 for the root. Whitespace may be spaces or line breaks.

Output: Print one index:count token per vertex in ascending index order, separated by single spaces. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• The parent array encodes one valid rooted tree.
• The root parent is -1; every other parent index is valid.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Accumulate one child count for every non-root parent index.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

4 -1 0 0 1

Sample output

0:2 1:1 2:0 3:0

Why the sample works: Visible walkthrough for the ordinary non-trivial path. Every non-root parent index contributes exactly one child to that parent. Input `4 -1 0 0 1` therefore produces `0:2 1:1 2:0 3:0`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: Trace the smallest non-trivial input and write the structure state after the operation before coding the loop.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.