- syllabus
- projects
- 24.1: iterators
- 24.2: templates
- 27.1: containers
- 27.2: containers
- 27.3: containers
- 27.4: containers
- 27.5: containers
- 28.1: arrayset
- 28.2: arrayset
- 29.1: recursion
- 30.1: sorting
- 31.1: linkedset
- 31.2: linkedset
- 26.1: list
- 26.2: list
- 32.1: stacks
- 32.2: stacks
- 32.3: stacks
- 33.1: queues
- 33.2: queues
- 33.3: queues
- 34.1: hashing
- 35.1: BST
- 36.1: balanced
- 37.1: heaps
- 37.2: heaps
- 37.3: heaps
- lessons
CS 10C Programming Concepts and Methodologies 2
Project 35.1
Complete and test a BST Validity Checker based on the partially completed files provided below.
Step 1: Inspect the Node.h file
Inspect the class declaration for a BST node in Node.h. Each node has a key, a left child pointer, and a right child pointer. The Node class includes a Parse() member function that takes a string parameter and creates a tree based on that parameter. The strings passed to Parse() are formatted as follows: Each node is in the form (key, leftChild, rightChild), where leftChild and rightChild can be nested nodes or "None". A leaf node is of the form (key). You are not allowed to modify this file
You'll notice that the provided code for this assignment does not follow a lot of our Style Conventions. For example, function names start with uppercase letters, and the entire class implementations are placed inside the class declaration in the header file. This will be good practice in reading code that is written a little differently. You should write your code to maintain the same practices that are used in the provided code.
Step 2: Implement the BSTChecker::CheckBSTValidity() function
Implement the CheckBSTValidity() function in the BSTChecker class in the BSTChecker.h file. The function takes the tree's root node as a parameter and returns the node that violates BST requirements, or nullptr if the tree is a valid BST.
A violating node will be one of three things:
- A node in the left subtree of an ancestor with a lesser key
- A node in the right subtree of an ancestor with a greater key
- A node with the left or right member variable pointing to an ancestor
Example:
If the input is:
(50, (25, None, (60)), (75))
which corresponds to the tree above, then the output is:
60
because 60 violates BST requirements by being in the left subtree of 50.
Example:
If the input is:
(20, (10), (30, (29), (31)))
which corresponds to the tree above, then the output is:
No violation
because all BST requirements are met.
The parse() function doesn't allow creating a tree with a node's child referencing an ancestor, so main() creates the trees manually to test that requirement.
Here are the files you'll need:
Documentation:
For this assignment, the file BSTChecker.h should be fully documented.