#lang lsl

;; Problem 1:
;;
;; A (height) balanced binary tree has a difference in height of the
;; left and right subtrees of at most 1, where height is the longest path to a leaf. Importantly,
;; this property (or _invariant_) must be mantained when inserting and removing elements
;; from the tree.
;;
;; Your task: define `balanced-prop` as a predicate.
;; You should test your property on several example trees using `check-expect`.
;; You're welcome to use the example trees we provide as some of your tests, but
;; you should also define some of your own.


;; part p1-a
(define-struct leaf [value])
(define-struct node [left right])
(define-contract (Tree X) (OneOf (Leaf X) (Node (Tree X) (Tree X))))
;; part p1-a

;; part p1-b
(define T1 (make-node (make-node (make-leaf 2)
                                 (make-leaf 3))
                      (make-leaf 4)))
;; part p1-b

;; part p1-c
(define T2 (make-node (make-node (make-node (make-leaf 1)
                                            (make-leaf 2))
                                 (make-leaf 3))
                      (make-leaf 4)))
;; part p1-c

;; part p1-d
(define T3 (make-node (make-node (make-leaf 1)
                                 (make-leaf 2))
                      (make-node (make-leaf 3)
                                 (make-leaf 4))))
;; part p1-d
(: balanced-prop (-> (Tree Integer) True))
(define (balanced-prop ...) ...)

(check-expect ...)
(check-expect ...)
(check-expect ...)
;; ...