#lang racket
 (require racket/trace)
(define (tree? t)
  (or (null? t)
      (and (list? t)
           (= (length t) 3))
           (tree? (cadr t))
           (tree? (caddr t))))
(define empty-tree '())
(define (make-tree root left right) (list root left right))      ; не искаме просто (define make-tree list) - защо?
(define (make-leaf root) (make-tree root empty-tree empty-tree)) ; за удобство
(define root-tree car)
(define left-tree cadr)
(define right-tree caddr)
(define empty-tree? null?)

(define t
  (make-tree 10
             (make-tree 7
                        (make-leaf 12)
                        (make-leaf 2))
             (make-tree 3
                        (make-tree 4
                                   (make-leaf 1)
                                   (make-leaf 2))
                        empty-tree)))

(define (tree-sum tree)
  (cond
    ((empty? tree) 0)
    (else (+ (root-tree tree) (tree-sum (left-tree tree)) (tree-sum (right-tree tree))))
  )
)

(define (tree-level level tree)
 (cond
   ((null? tree) '())
   ((= level 0) (list (root-tree tree)))
   (else (append (tree-level (- level 1) (left-tree tree)) (tree-level (- level 1) (right-tree tree))))
  )
  )

(define (all-levels tree)
  (define (all-levels-iter tree lvl)
    (if (empty? (tree-level lvl tree)) '()
     (cons (tree-level lvl tree) (all-levels-iter tree (+ 1 lvl))))
    )
(all-levels-iter tree 0)
)

(define (tree-map f t)
  (cond
    ((empty? t ) '())
    (else (list  (f (root-tree t))  (tree-map f (left-tree t) ) (tree-map f (right-tree t))))))

(define (tree->list t)
  (cond
    ((empty? t) '())
    (else (append  (tree->list (left-tree t)) (list (car t))  (tree->list (right-tree t)))))
  )

;Да се напише функция (bst-insert val t), която вмъква стойността val в двоичното наредено дърво t.