PAT Advanced 1110 Complete Binary Tree

Overview

PAT Advanced 1110 Complete Binary Tree: BFS the tree and count the number of nodes at i-th level, it should be 2^i, last level should be consecutive from left to right.

PAT Advenced 1110 Complete Binary Tree Problem

Given a tree, you are supposed to tell if it is a complete binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=20) which is the total number of nodes in the tree – and hence the nodes are numbered from 0 to N-1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a “-“ will be put at the position. Any pair of children are separated by a space.

Output Specification:

For each case, print in one line “YES” and the index of the last node if the tree is a complete binary tree, or “NO” and the index of the root if not. There must be exactly one space separating the word and the number.

Sample Input 1:

9
7 8
- -
- -
- -
0 1
2 3
4 5
- -
- -

Sample Output 1:

YES 8

Sample Input 2:

8
- -
4 5
0 6
- -
2 3
- 7
- -
- -

Sample Output 2:

NO 1

PAT Advenced 1110 Complete Binary Tree Algorithm

The algorithm is not too difficult to come up with, BFS the tree and count the number of nodes at each level, for i-th level, the number of nodes should be 2^i except the last level, however, the last level should contain the nodes from left to right and there should not be a hole, for example, the following tree is not a complete binary tree:

          0
       /     \
      1       2
     / \     / \
    5   6       7

The following is the C++ source code that could be accepted by PAT OJ to pass this PAT Advenced 1110 Complete Binary Tree Problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <string>
#include <utility> 
#include <queue> 
#include <algorithm> 

struct Node {
	int l;
	int r;
public:
	Node() : l(-1), r(-1) {}
};


Node nodes[21];
bool flag[21];


std::pair<bool, int> bfs(int r) {
	std::queue<int> *q0 = new std::queue<int>;
	std::queue<int> *q1 = new std::queue<int>;
	q0->push(r);
	std::pair<bool, int> result(false, r);
	int l = r;
	int ec = 1;
	while (q0->size() != 0) {
		int as = q0->size();
		bool f = false;
		while (q0->size() != 0) {
			int curr = q0->front(); q0->pop();
			if (nodes[curr].l != -1) {
				if (f) {
					return result;
				} else {
					l = nodes[curr].l;
					q1->push(l);
				}
			} else {
				f = true;
			}

			if (nodes[curr].r != -1) {
				if (f) {
					return result;
				} else {
					l = nodes[curr].r;
					q1->push(l);
				}
			} else {
				f = true;
			}
		}

		if (q1->size() != 0 && ec != as) {
			return result;
		}

		std::queue<int> *t = q0;
		q0 = q1;
		q1 = t;
		ec *= 2;
	}

	result.first = true;
	result.second = l;
	return result;
}


int main() {
	int n;
	std::cin >> n;

	int r = -1;
	std::string c1, c2;
	int v;
	for (int i = 0; i < n; ++i) {
		flag[i] = true;
	}

	for (int i = 0; i < n; ++i) {
		nodes[i].l = nodes[i].r = -1;
		std::cin >> c1 >> c2;
		if (c1.at(0) != '-') {
			v = atoi(c1.c_str());
			nodes[i].l = v;
			flag[v] = false;
		}

		if (c2.at(0) != '-') {
			v = atoi(c2.c_str());
			nodes[i].r = v;
			flag[v] = false;
		}
	}
	for (int i = 0; i < n && r < 0; ++i) {
		if (flag[i]) {
			r = i;
		}
	}

	std::pair<bool, int> ret = bfs(r);
	if (ret.first) {
		std::cout << "YES " << ret.second << std::endl;
	} else {
		std::cout << "NO " << ret.second << std::endl;
	}

	return 0;
}

Summary

PAT Advanced 1110 Complete Binary Tree is testing BFS, so BFS the tree and count the number of nodes at i-th level, it should be 2^i, last level should be consecutive from left to right.

Written on September 16, 2016