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.

Written on November 19, 2016