(define-struct node (left right))

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


(define (tree-grow-min tree)
  (cond
    [(empty? tree) (make-node empty empty)]
    [(= 1 (getNumNodes tree)) (make-node (make-node empty empty) empty)]
    [(= 2 (getNumNodes tree)) (make-node (make-node empty empty) (make-node empty empty))]
    [(isFull (getNumNodes tree) 1) (makeFullTree (getFullHeight (+ (getNumNodes 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 (getNumNodes tree)) empty]
    [(= 2 (getNumNodes tree)) (make-node empty empty)]
    [(isFull (getNumNodes tree) 1) (makeFullTree (getFullHeight (- (getNumNodes tree) 1) 0) (make-node empty empty))]
    [(< (getHeight (node-left tree)) (getHeight (node-right tree)))
      (make-node (tree-shrink-min (node-right tree)) (node-left tree))]
    [true (make-node (tree-shrink-min (node-left tree)) (node-right 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 is a power of 2 (in other words, if n number of nodes makes a full tree
(define (isFull n count)
  (cond
    [(= 1 n) #t]
    [(< n (expt 2 count)) #f]
    [else (isFull (/ n (expt 2 count)) (+ 1 count))]))

; given number of nodes, gets height (in full levels) of tree
(define (getFullHeight n count)
  (cond
    [(< n (expt 2 count)) count]
    [else (getFullHeight (/ n (expt 2 count)) (+ 1 count))]))

; given tree, gets number of nodes in tree
(define (getNumNodes tree)
  (cond
    [(empty? tree) 0]
    [else (+ 1 (getNumNodes (node-left tree)) (getNumNodes (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))]))