#lang racket
;; LISTA 4 - skomplikowane predykaty oraz predykaty i łączące je twierdzenia o indukcji
; w szczegolnosci jesli chodzi o listy i drzewa


(define (mirror tree) ;3
  (if (leaf? tree)
      tree
      (make-node (node-val tree )
                 (mirror (node-right tree))
                 (mirror (node-left tree)))))

(define (flatten tree) ;4
  (if (leaf? tree)
      null
      (append (flatten (node-left tree))
            (cons (node-val tree)
                  (flatten (node-right tree))))))

(define (treesort xs) ;5
  (define (treesorcik xs tree)
    (if (null? xs)
        tree
       (treesorcik (cdr xs) (bst-insert (car xs) tree))))
  (flatten (treesorcik xs 'leaf)))





;; Z WYKLADU

;;; drzewa binarne

(define (leaf? x)
  (eq? x 'leaf))

(define leaf 'leaf)

(define (node? x)
  (and (list? x)
       (= (length x) 4)
       (eq? (car x) 'node)))

(define (node-val x)
  (cadr x))

(define (node-left x)
  (caddr x))

(define (node-right x)
  (cadddr x))

(define (make-node v l r)
  (list 'node v l r))

(define (tree? t)
  (or (leaf? t)
      (and (node? t)
           (tree? (node-left t))
           (tree? (node-right t)))))

;;; wyszukiwanie i wstawianie w drzewach przeszukiwań binarnych

(define (bst-find x t)
  (cond [(leaf? t)          false]
        [(= x (node-val t)) true]
        [(< x (node-val t)) (bst-find x (node-left t))]
        [(> x (node-val t)) (bst-find x (node-right t))]))

(define (bst-insert x t)
  (cond [(leaf? t)
         (make-node x leaf leaf)]
        [(< x (node-val t))
         (make-node (node-val t)
                    (bst-insert x (node-left t))
                    (node-right t))]
        [else
         (make-node (node-val t)
                    (node-left t)
                    (bst-insert x (node-right t)))]))