Application lab in Binary Trees and Traversals

Mission

Count nodes with no left or right child.

Learning outcome: Apply recursion to count leaves

Correctness contract

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

Required technique: Return one only for a node with no children; otherwise combine counts from both subtrees.

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

Input and output

Input: n followed by n triples: nodeValue leftChildIndex rightChildIndex; -1 means no child. Whitespace may be spaces or line breaks.

Output: Print the single exact numeric result with no label. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• Node 0 is the root.
• Child indexes are -1 or valid indexes, and the encoding is an acyclic binary tree.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Return one only for a node with no children; otherwise combine counts from both subtrees.
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

3 A 1 2 B -1 -1 C -1 -1

Sample output

2

Why the sample works: Visible walkthrough for the ordinary non-trivial path. Only nodes with neither child contribute one; internal nodes combine the two subtree counts. Input `3 A 1 2 B -1 -1 C -1 -1` therefore produces `2`.

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.