For this challenge, you are giving a series of binary trees and you are to check if each given binary tree is also a binary search tree. Recall that a binary search tree is a binary tree such that:
The value at a node is never less than an entry in its left subtree.
The value at a node is less than every entry in its right subtree.
For instance, the tree to the right is in fact a binary search tree.
Note, this problem is inspired by Problem 4.5 from Cracking the Code Interview.
You will be given a series of trees specified in Breadth First Search order from standard input:
N N_0 N_1 ... N_N-1
The first number of each line is the number of nodes in the binary tree.
The remaining numbers are the values for each node.
Any nodes with the value -1
are considered empty nodes (ie. they don't exist).
For each tree, you should output the message:
Tree N is a BST
if the binary tree is a binary search tree. Otherwise, you should output:
Tree N is not a BST
Note, N
is the tree number in the order in each it was read (starting from 1
).
Given the following input:
2 20 20 3 20 -1 20 14 8 3 10 1 6 -1 14 -1 -1 4 7 -1 -1 13
Your program should output the following:
Tree 1 is a BST Tree 2 is not a BST Tree 3 is a BST
You can easily store the tree using an array based representation.
You should consider a recursive solution that ensures the [binary search tree] invariant is maintained.
To submit your solution, you must initiate a Merge Request in your private assignments repository and assign it to the appropriate TA from the Challenge 05 - TA assignment list.
To facility the Merge Request workflow, you must do your development in its own branch:
$ cd path/to/repo # Go to your repository $ git checkout master # Make sure we are on master branch $ git pull # Make sure we have changes for GitLab $ git pull upstream master # Fetch and merge upstream changes $ git checkout -b challenge05 # Create challenge05 branch ... # Do your work $ git commit # Commit your work (can do this multiple times) $ git push -u origin challenge05 # Push branch to GitLab