# 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.