# PAT Advanced 1115 Counting Nodes in a BST

## Overview

PAT Advanced 1115 Counting Nodes in a BST tests BST insertion and then BFS to get the number of nodes in the lowest 2 levels of the resulting tree.

## PAT Advenced 1115 Counting Nodes in a BST

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

The left subtree of a node contains only nodes with keys less than or equal to the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees. Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.

**Input Specification:**

Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000) which is the size of the input sequence. Then given in the next line are the N integers in [-1000 1000] which are supposed to be inserted into an initially empty binary search tree.

**Output Specification:**

For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format:

n1 + n2 = n

where n1 is the number of nodes in the lowest level, n2 is that of the level above, and n is the sum.

**Sample Input:**

9 25 30 42 16 20 20 35 -5 28

**Sample Output:**

2 + 4 = 6

## PAT Advenced 1115 Counting Nodes in a BST Solution

First construct the BST by insert each node in the order of the input, this takes O(N^2) time worst, but the input is <=1000 so, this should be fine, after geting the resulting tree, breadth first search the three and get the nodes of the lowest 2 levels. No tricky issues that we need to be concerned about.

The following is the C++ source code that could be accepted by PAT OJ to pass this PAT Advenced 1115 Counting Nodes in a BST:

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

#include <cstdio>
#include <queue>
using std::queue;
struct TN {
int val;
TN *left;
TN *right;
TN(int v) : val(v), left(NULL), right(NULL) {}
};
class BST {
private:
TN *root;
public:
BST() : root(NULL) { }
void insert(int v) {
root = insertInner(v, root);
}
void gao() {
int l = 0, sl = 0, cu = 0;
queue<TN*> *q1 = new queue<TN*>;
queue<TN*> *q2 = new queue<TN*>;
queue<TN*> *t;
q1->push(root);
while (!q1->empty()) {
cu = q1->size();
while (!q1->empty()) {
TN *node = q1->front(); q1->pop();
if (node->left) {
q2->push(node->left);
}
if (node->right) {
q2->push(node->right);
}
}
t = q1;
q1 = q2;
q2 = t;
sl = l;
l = cu;
}
printf("%d + %d = %d", l, sl, l + sl);
}
private:
TN *insertInner(int v, TN *r) {
if (NULL == r) {
return new TN(v);
} else {
if (v <= r->val) {
r->left = insertInner(v, r->left);
} else {
r->right = insertInner(v, r->right);
}
return r;
}
}
};
int main() {
BST bst;
int n, v;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &v);
bst.insert(v);
}
bst.gao();
return 0;
}

## Summary

PAT Advanced 1115 Counting Nodes in a BST tests BST insertion and then BFS to get the number of nodes in the lowest 2 levels of the resulting tree.