# Specification of program "bst"

###### tags: `etsiinf`

## Name

bst - Verifies if a provided list of numbers represent a valid binary search tree.

## Usage

bst input-file [options]

## Description

**bst** reads a **list of integers** from an input file and verifies a if the provided **integer** values build a valid [binary search tree](https://en.wikipedia.org/wiki/Binary_search_tree) (BST) when visited following a [breadth-first search](https://en.wikipedia.org/wiki/Breadth-first_search). The result tree is printed with each level in a different line.

The presented tree, which is a valid BST, would be represented by the following input string: `10 6 18 4 8 15 21`

On the other hand, this image, that would be represented by `1 2 3 4 5 6 7`, does not represent a valid BST

The program should visit this string provided in a text file and print `valid` or `invalid`.

Tree representation follows this logic:

## Options

Options should be provided through the command line.

- ```-f[ile] <filename>``` - redirect the program output to the specified file.

The options below should only be executed if the given tree is a valid binary search tree. Each operation should print the result in a new line. Each presented expected output takes the valid BST image shown in the `Description` as reference.

- ```-t[op]``` - prints the top view of the tree. Expected output `top: 4 6 10 18 21`
- ```-b[ottom]``` - prints the bottom view of the tree. `bottom: 4 8 15 21`
- ```-r[ight]``` - prints the right side view of the tree. `right: 10 18 21`
- ```-l[eft]``` - prints the left side view of the tree. `left: 10 6 4`
- ```-d[iameter]``` - prints the diameter of the tree. Expected output (one of the following):
- `diameter: 4 6 10 18 21`
- `diameter: 4 6 10 18 15`
- `diameter: 8 6 10 18 21`
- `diameter: 8 6 10 18 15`
- ```-h[eight]``` - prints the height of the tree. Expected output `height: 3`

## Input Data

- File containing a **list of integers** (the string provided in the input file must not contain floating point numbers or anything that isn't an integer) separated by a space.
- If the file contains something different from integers the following message should be printed: `[ERROR] All provided items should be integers!`
- No number must exceed 10000.
- If the this limit is exceeded the following message should be printed: `[ERROR] Provided numbers should not exceed 10000!`
- The provided binary tree must be **complete** (every parent node has 2 and only 2 children nodes). In complete binary trees the number of elements equals to `2^h – 1` where `h` is the height of the tree. The tree should not have a height superior to 10, meaning that the number of provided elements should not exceed 1023 (2^10 - 1).
- If the provided tree is not complete, the following message should be printed: `[ERROR] The provided list of numbers should build a complete binary tree!`

## Limitations

- The commands that are passed on the command line must be the same as in the specification, or the program will not function correctly.