We\'ve been given code for a binary tree data type: data BinaryTree = Branch Int

Question

We've been given code for a binary tree data type:

data BinaryTree = Branch Integer BinaryTree BinaryTree
| Leaf
deriving (Show, Ord, Eq)

As well as code to create an arbitrary binary tree (not necessarily a BST), and a function that takes a binary tree and returns a boolean based on whether the tree is a BST.

We've also been given five insert functions, four of which are wrong, and we are meant to write a series of quickCheck properties to test if the function is correct or not. I've worked out (at least I think) what is wrong with each function. Problem is, I'm not sure exactly how to go about writing these tests.

What I've come up with so far: insert3 doesn't work when a number was already been inserted into the tree, it doesn't do anything (we've been told the same values can occur, and to add them to the right hand side of the tree), insert2 doesn't handle the case of nodes being equal at all, and insert4 branches the wrong way.

For a property that fails insert3, I'm thinking I test that tree and insertFunction tree should not be the same. For insert2 I'm thinking that I just test that inserting into a BST should result in a BST.

Any help would be appreciated, thanks. I can provide the other bits of code we've been given if needed, but in the interest of keeping this post shorter, I haven't yet.

-- insert functions
insert1 :: Integer -> BinaryTree -> BinaryTree
insert1 i Leaf = Leaf
insert1 i (Branch v l r)
| i < v = Branch v (insert1 i l) r
| otherwise = Branch v l (insert1 i r)

insert2 :: Integer -> BinaryTree -> BinaryTree
insert2 i Leaf = Branch i Leaf Leaf
insert2 i (Branch v l r)
| i < v = Branch v (insert2 i l) r
| i > v = Branch v l (insert2 i r)

insert3 :: Integer -> BinaryTree -> BinaryTree
insert3 i Leaf = Branch i Leaf Leaf
insert3 i (Branch v l r)
| i < v = Branch v (insert3 i l) r
| i == v = Branch v l r
| i > v = Branch v l (insert3 i r)

insert4 :: Integer -> BinaryTree -> BinaryTree
insert4 i Leaf = Branch i Leaf Leaf
insert4 i (Branch v l r)
| i < v = Branch v l (insert4 i r)
| otherwise = Branch v (insert4 i l) r

insert5 :: Integer -> BinaryTree -> BinaryTree
insert5 i Leaf = Branch i Leaf Leaf
insert5 i (Branch v l r)
| i < v = Branch v (insert5 i l) r
| otherwise = Branch v l (insert5 i r)

Explanation / Answer

HI, hope you find my post useful and you rate it a lifesaver! So, I decided not to put any code here, as the functions should be quite straightforward. Instead, I will give hints how to solve the quick checks. I don't know if you need one for each function or one in general. I will start from one for each, and then one for all. FUncion 1. Incorrect, as it does nothing, does not insert anything. Check: Write a size function for a binary tree, counting nodes. have arbitrary binary tree, insert using first function, and chack is if size is greater by one after insertion. it is not! Function 2. Insert a node which is equal to one already in the tree (you can take the one from the first branch) and see an error. Function 3. Number already in the tree... Take any number already in the tree as above (first node fir instance) and insert. Then check that size should be greater by 1. Function 4. Inserts wrong way around. You can use function to check if it is a BST trivially. Now, this is fine, but we might ask a general rule for this algo, to check all cases of errors. So what does it produce, given a list of numbers? A tree, with the same number of nodes WITH ORDERING. SO, if we flatten the tree (turn it back to a list) we will get a sorted list of the same size as initial one. SO let's check that the two lists are equal (one operator in haskell). Done! Hope you enjoyed

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.