(define-struct node (left right))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (tree-grow-min tree)
  (cond
    [(empty? tree) (make-node empty empty)]
    [(= 1 (getnodes tree)) (make-node (make-node empty empty) empty)]

    [(isFull (getnodes tree))
      (cond
        [(= 2 (getnodes tree)) (make-node (make-node empty empty) (make-node empty empty))]
        [true (makeFullTree (getFullHeight (+ (getnodes tree) 1) 0) (make-node empty empty))])]

    [(> (getHeight (node-left tree)) (getHeight (node-right tree)))
      (make-node (tree-grow-min (node-right tree)) (node-left tree))]
    [true (make-node (tree-grow-min (node-left tree)) (node-right tree))]))


(define (tree-shrink-min tree)
  (cond
    [(empty? tree) empty]
    [(= 1 (getnodes tree)) empty]

    [(isFull (getnodes tree))
      (cond
        [(= 2 (getnodes tree)) (make-node empty empty)]
        [true (makeFullTree (getFullHeight (- (getnodes tree) 1) 0) (make-node empty empty))])]

    [(< (getHeight (node-left tree)) (getHeight (node-right tree)))
      (make-node (node-left tree) (tree-shrink-min (node-right tree)))]
    [true (make-node (node-right tree) (tree-shrink-min (node-left tree)))]))

; gets height (basic) of tree)
(define (getHeight tree)
  (cond
    [(empty? tree) 0]
    [else (+ 1 (max (getHeight (node-left tree)) (getHeight (node-right tree))))]))

; checks if n number of nodes makes a full tree
(define (isFull n)
  (if (= n 1) true (if (= 0 (modulo n 2)) (isFull (/ n 2)) false )))

; given number of nodes, gets height (in full levels) of tree
(define (getFullHeight n count)
  (cond
    [(= n 0) 0]
    [(= n 1) (+ 1 count)]
    [true (getFullHeight (- (/ (+ 1 n) 2) 1) (+ 1 count))]))

; given tree, gets number of nodes in tree
(define (getnodes tree)
  (cond
    [(empty? tree) 0]
    [else (+ 1 (getnodes (node-left tree)) (getnodes (node-right tree)))]))

; make a full tree
(define (makeFullTree height tree)
  (cond
    [(= height 0) empty]
    [(= height 1) tree]
    [true (makeFullTree (- 1 height) (make-node tree tree))]))