-- :cd C:\sz\dit\pkd\Labs
-- In collaboration with Simon Wallbing

-- PROBLEM 1a:
--------------
-- a) Write a function delete :: BSTree -> Int -> BSTree that implements the above algorithm to delete a label
-- from a binary search tree. Here, binary search trees (i.e., type BSTree) are defined as in the lecture:
-- 
--   data BSTree = Void | Node BSTree Int BSTree   deriving (Show)
-- 
-- Hint: For step 1. of the algorithm, write an auxiliary function that efficiently finds the largest label
-- in a (non-empty) binary search tree
-- 
-- b) Test your function by deleting the label 7 from the binary search tree that is depicted on the left in 
-- the upper figure. (Optionally: perform this test using HUnit.)


{- 1.a.0 A data type for representing a binary tree. The empty binary tree is given by Void.
  - A non-empty binary tree with label x is given by (Node l x r), where l is the left subtree
  and r is the right subtree. (Source: lecture '17-Binary-Search-Trees.pdf', page 7.)
  INVARIANT: -
  EXAMPLES:
    (Node (Node Void 4 Void) 5 (Node Void 6 Void))
    (Node (Node Void 0 Void) 1 (Node Void 2 Void))
    (Node (Node Void 5 Void) 7 (Node Void 8 Void))
    (Node (Node (Node Void 0 Void) 1 (Node Void 2 Void)) 3 (Node (Node Void 5 Void) 7 (Node Void 8 Void)))
    (Node Void 8 Void)
    (Node (Node (Node Void 4 Void) 5 (Node Void 6 Void)) 7 (Node Void 8 Void))
    (Node 
      (Node (Node Void 0 Void) 1 (Node Void 2 Void))
      3
      (Node (Node (Node Void 4 Void) 5 (Node Void 6 Void)) 7 (Node Void 8 Void)))

    Node BSTree i BSTree
    Node Void i Void
-}
data BSTree = Void | Node BSTree Int BSTree   deriving (Show)
-- data BSTree = Void | Node BSTree Int BSTree  deriving (Show)