Contest Python: USACO Bronze › Unit 12 — Binary Trees & Traversals
Exercises: Unit 12 — Binary Trees & Traversals
Each problem is a program that reads the whole input from stdin and prints the exact output (real contest style — no solve() wrapper): import sys; data = sys.stdin.read(), parse the tree into parallel arrays, then print. A -1 child means "none" — check it before indexing. Write each program in a .py file and run it with piped input, e.g. python my_solution.py < case.txt.
Exercise 1: Record Inspection Order
Print the node values in pre-order: visit the node, then its left subtree, then its right subtree. Separate values with one space. The sample tree is deliberately uneven: its pre-order, in-order, and post-order sequences are all different, and the final value 13 is reached only after following the right subtree correctly.
Constraints. 1 <= N <= 1000, 0 <= root < N, and the tree height is at most 300.
Every value is a distinct integer between -1000000000 and 1000000000.
Every non--1 child index is between 0 and N - 1, and all N nodes belong to one binary tree rooted at root.
Use recursive pre-order traversal; sorting the values does not produce the required order.
Sample Input
7 0
8 1 2
3 3 4
10 -1 5
1 -1 -1
6 -1 -1
14 6 -1
13 -1 -1Sample Output
8 3 1 6 10 14 13How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 2: Tallest Reporting Chain
Print the tree's height: the number of nodes on its longest path from the root to a leaf. An empty child has height 0, so a leaf has height 1. The sample is a left-only tree whose final node makes the height 4.
Constraints. 1 <= N <= 1000, 0 <= root < N, and the tree height is at most 300.
Every value is an integer between -1000000000 and 1000000000.
Every non--1 child index is valid, and all nodes form one binary tree rooted at root.
Compute the height with a recursive walk of the child indices.
Sample Input
4 0
9 1 -1
7 2 -1
4 3 -1
2 -1 -1Sample Output
4How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 3: Terminal Record Count
A leaf is a node whose left and right child indices are both -1. Print the number of leaves in the tree. Do not count one missing child of a non-leaf as a leaf. In the sample, the last listed node is the third leaf.
Constraints. 1 <= N <= 1000, 0 <= root < N, and the tree height is at most 300.
Every value is an integer between -1000000000 and 1000000000.
Every non--1 child index is valid, and all nodes form one binary tree rooted at root.
Count leaves with a recursive traversal.
Sample Input
6 0
20 1 2
9 3 4
30 -1 5
4 -1 -1
12 -1 -1
35 -1 -1Sample Output
3How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.
Exercise 4: Score Summary
Print three integers separated by spaces: the sum, minimum, and maximum of all node values. A missing subtree contributes the sum identity 0; choose safe identities outside the legal value range for minimum and maximum. The sample is the single-node boundary case.
Constraints. 1 <= N <= 1000, 0 <= root < N, and the tree height is at most 300.
Every value is an integer between -1000000000 and 1000000000.
Every non--1 child index is valid, and all nodes form one binary tree rooted at root.
Compute all three aggregates with a recursive traversal.
Sample Input
1 0
42 -1 -1Sample Output
42 42 42How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 5: BST Membership
The first line contains N root target. The remaining N lines describe a valid binary search tree with distinct values. Print YES if target is stored in the tree and NO otherwise. Recursively compare at one node and follow only the left or right child that could contain the target. The sample is a right-only tree, and the decisive target is stored in its final node.
Constraints. 1 <= N <= 1000, 0 <= root < N, and the BST height is at most 300.
Every node value and target is between -1000000000 and 1000000000.
Every non--1 child index is valid, and all nodes form one binary tree rooted at root.
All stored values are distinct and obey the BST ordering property.
Sample Input
4 0 11
2 -1 1
5 -1 2
9 -1 3
11 -1 -1Sample Output
YESHow this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 6: Build the Search Index
The first line contains N, and the second line contains N distinct keys in insertion order. Start with an empty BST whose root is -1. Recursively insert each key: smaller keys go left and larger keys go right. Then print the finished tree's pre-order traversal with one space between keys. The first inserted key becomes the root. The final input key 13 must appear last in the sample output; sorting the keys would erase the required tree shape.
Constraints. 1 <= N <= 1000, every key is distinct and between -1000000000 and 1000000000, and the resulting BST height is at most 300.
Build the BST with parallel value, left-child, and right-child arrays.
Use recursive insertion and recursive pre-order traversal.
Sample Input
8
8 3 10 1 6 14 4 13Sample Output
8 3 1 6 4 10 14 13How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.
Exercise 7: Validate the Search Index
Print VALID if the given binary tree obeys the strict BST ordering property and INVALID otherwise. Values are distinct. Recursively propagate an open (low, high) interval: every node must be greater than its low bound and smaller than its high bound. Checking only parent and child is not enough. In the sample, value 9 is inside the left subtree of 8, so the deep violation makes the answer invalid.
Constraints. 1 <= N <= 1000, 0 <= root < N, and the tree height is at most 300.
Every value is a distinct integer between -1000000000 and 1000000000.
Every non--1 child index is valid, and all nodes form one binary tree rooted at root.
Validate with recursive propagated bounds and separate comparisons.
Sample Input
5 0
8 1 2
3 -1 3
10 -1 4
9 -1 -1
14 -1 -1Sample Output
INVALIDHow this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 8: Closing Audit Order
Print the values in post-order: recursively traverse the left subtree, then the right subtree, then visit the node. Separate values with one space. The sample tree distinguishes pre-order, in-order, and post-order; its root 8 is deliberately the final output value.
Constraints. 1 <= N <= 1000, 0 <= root < N, and the tree height is at most 300.
Every value is a distinct integer between -1000000000 and 1000000000.
Every non--1 child index is valid, and all nodes form one binary tree rooted at root.
Use recursive post-order traversal; sorting the values does not produce the required order.
Sample Input
7 0
8 1 2
3 3 4
10 -1 5
1 -1 -1
6 -1 -1
14 6 -1
13 -1 -1Sample Output
1 6 3 13 14 10 8How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 9: Target Record Depth
The first line contains N root target. All node values are distinct, and target is guaranteed to occur. Print its depth, counting the root as depth 1. Recursively walk the tree and treat a missing subtree as 0; a positive result tells an ancestor which branch found the target. The sample is right-only, and its final node has depth 5.
Constraints. 1 <= N <= 1000, 0 <= root < N, and the tree height is at most 300.
Every node value and target is between -1000000000 and 1000000000.
Every non--1 child index is valid, and all nodes form one binary tree rooted at root.
Use a recursive traversal; do not assume the tree is a BST.
Sample Input
5 0 21
4 -1 1
8 -1 2
15 -1 3
16 -1 4
21 -1 -1Sample Output
5How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.