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

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