;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Binary Tree ADT from the book
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define make-empty-tree
  (lambda () '()))

(define make-nonempty-tree
  (lambda (root left-subtree right-subtree)
    (list root left-subtree right-subtree)))

(define empty-tree? null?)

(define root car)

(define left-subtree cadr)

(define right-subtree caddr)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; All else are mine
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; A useful constructor
;; Make a singleton tree
(define make-singleton-tree
  (lambda (value)
    (make-nonempty-tree value (make-empty-tree) (make-empty-tree))))

;; count the number of nodes in the binary tree "tree"
(define num-nodes
  (lambda (tree)
    (if (empty-tree? tree)
        0
        (+ 1
           (num-nodes (left-subtree tree))
           (num-nodes (right-subtree tree))))))

;; pretty-print a tree
(define pretty-print
  (lambda (tree)
    (print tree 0)))

(define print
  (lambda (tree depth)
    (cond ((empty-tree? tree)
           (newline))
          (else
           (print (right-subtree tree) (+ 1 depth))
           (print-node (root tree) depth)
           (print (left-subtree tree) (+ 1 depth))))))

(define print-node
  (lambda (value indent-level)
    (cond ((= indent-level 0)
           (display value)
           (newline))
          (else
           (display "    ")
           (print-node value (- indent-level 1))))))

;; randomly insert the key value into tree
(define random-insert
  (lambda (tree value)
    (let ((t (make-singleton-tree value)))
      (cond ((empty-tree? tree) t)
            ((= (random 2) 0)
             (make-nonempty-tree (root tree) 
                                 (if (empty-tree? (left-subtree tree))
                                     t
                                     (random-insert (left-subtree tree) value))
                                 (right-subtree tree)))
            (else
             (make-nonempty-tree (root tree) 
                                 (left-subtree tree)
                                 (if (empty-tree? (right-subtree tree))
                                     t
                                     (random-insert (right-subtree tree) value))))))))

;; Generate a random binary tree.
;; Note: The shape of the generated tree is random; the placement of keys is not.
(define generate-random-tree
  (lambda (n)
    (if (= n 0)
        (make-empty-tree)
        (random-insert (generate-random-tree (- n 1)) n))))