USACO BRHS10A Problem 'printtree' Analysis

by Damon Doucet

The bulk of this problem lies in its recursive printing. First, we read all of the parents, then decide which node to start at (whichever node has a parent of -1), and call our print() function with that.

Our print function takes two parameters--the node, and the level; the node is what to print, and the level is how far out to print it (how many '.'s to give it). We initially call it with (root, 0), because--as mentioned in the text--the root has level 0.

In our print() function, we first print all of the necessary dots, and then our node, then loop through all of the nodes in the tree. If any node has our current node listed as its parent, then we call print() with the parameters of that new node and the current level + 1.

Here's the code:

#include <fstream>
using namespace std;

ifstream fin("printtree.in");
ofstream fout("printtree.out");

int N, parent[505];
void print(int node, int level);

int main() {
	int i, root;

	fin >> N;
	for (i = 1; i <= N; i++) { //be sure to use 1-based indexing here
		fin >> parent[i];
		if (parent[i] == -1)
			root = i;
	}

	print(root, 0);
	return 0;
}

void print(int node, int level) {
	int i;
	for (i = 0; i < level; i++)
		fout << ".";
	fout << node << "\n";

	//now print the children
	for (i = 1; i <= N; i++)
		if (parent[i] == node)
			print(i, level + 1);
}

Additionally, since you are told that this is a binary tree, you can optimize it into the following longer but faster solution.

#include <fstream>
using namespace std;

ifstream fin("printtree.in");
ofstream fout("printtree.out");

int N, children[505][2];
void print(int node, int level);

int main() {
	int i, parent, root;

	for (i = 1; i <= N; i++)
		children[i][0] = children[i][1] = -2; //no child

	fin >> N;
	for (i = 1; i <= N; i++) {
		fin >> parent;
		if (parent == -1) root = i;
		else {
			if (children[parent][0] == -2)
				children[parent][0] = i;
			else //that spot is already taken; fill the other one
				children[parent][1] = i;
		}
	}

	print(root, 0);
	return 0;
}

void print(int node, int level) {
	int i;
	for (i = 0; i < level; i++)
		fout << '.';
	fout << node << "\n";

	if (children[node][0] != -2) {
		print(children[node][0], level + 1);
		if (children[node][1] != -2)
			print(children[node][1], level + 1);
	}
}