Binary Search Tree in Scheme

;Impliementing tree. and thus binary searching.....


;Checks whether the given node is a leaf...
(define (leaf? tree)
 (if (and (null? (left-branch tree) (null? right-branch tree)))
   #t
   #f
 )
)
;Checks wheter the tree has only left branch
(define (left-only? tree)
 (if (and (null? (right-branch tree)) (not (null? (left-branch tree))))
   #t
   #f
 )

)

;Checks wheter the tree has only left branch
(define (right-only? tree)
 (if (and (null? (left-branch tree)) (not (null? (right-branch tree))))
   #t
   #f
 )

)


;When node, left branch and right branch of the tree are passed as arguements, 
;the function will make and return the tree
(define (make-tree node left-branch right-branch)
    (list node left-branch right-branch)
)


;This function returns the node element of a given tree
(define (node tree)
    (car tree)

)

;This function returns the left branch(subtree) of a given tree
(define (left-branch tree)
    (cadr tree)
)


;This function returns the right branch(subtree) of a given tree
(define (right-branch tree)
    (caddr tree)
    
)


;This function will insert an element into a tree and returns the new tree
(define (insert e tree)
    (cond
        ((null? tree) (make-tree e '() '()));If the passed tree is null then a new tree of the form (e '() '())
                                            ;will be created
                        
        ((= e (node tree)) tree) ; If the node of the element is eqaual to the elemented to be inserted
                                    ; Then there is no need for inserting and the previous tree will be returned.
    
        ;If the element is greater than the node element, then the element shud be inserted 
        ;somewhere in the right-branch        
        ((> e (node tree)) 
            (make-tree (node tree) (left-branch tree) (insert e (right-branch tree)))
        ) 
    
        ;If the element is greater than the node element, then the element shud be inserted 
        ;somewhere in the left-branch  
        ((< e (node tree))
    
            (make-tree (node tree) (insert e (left-branch tree)) (right-branch tree))
    
        )
    
    
    )
)

;This function is called to make a tree from a given list..
;It will call the function set->tree2 with cdr of set and a new tree with root node (car set) as arguement
(define (set->tree set)
    (if (null? set)
        '()
        (set->tree2 (cdr set) (make-tree (car set) '() '()))    
    
    )
)


;This functon will extract each element of set and insert it into the given tree
(define (set->tree2 set tree)
    (if (null? set)
        tree
        (set->tree2 (cdr set) (insert (car set) tree))
    )

)


;Searching an element in a binary search tree..
(define (search-tree e tree)
    (cond
        ((null? tree) #f) ; If the set is null result is boolean false
        ((= (node tree) e) #t) ; If the node of tree equals e, the result is true
        ((> e (node tree)) (search-tree e (right-branch tree))); if e is greater than node element, it shud be searched in right-branch
        ((< e (node tree)) (search-tree e (left-branch tree))) ; if e is lesser than node element, it shud be searched in right-branch
        
        
    )
    
)


;The function which user calls for searching element in a set,
;It will call the functions make the set to a binary search tree and then to perform binary search
(define (search e set)

    (search-tree e (set->tree set))
    
)

;Inserting tree1 into ertreme right of tree2(function used while deletion...)..

(define (join-trees tree1 tree2)
 (if (null? tree2)
    tree1
    (make-tree (node tree2) (left-branch tree2) (join-trees tree1 (right-branch tree2)))
 )
)

;Function to delete an element from a tree..

(define (delete e tree)
 (if (null? tree)
  '()

  ;If the tree is not null then....
  (cond  ((= e (node tree))
     (cond ((leaf? tree)
        '()
      )
      
      ((left-only? tree)
       (left-branch tree)
      
      )
      ((right-only? tree)
       (right-branch tree)
      
      )
      (else 
       (join-trees (right-branch tree) (left-branch-tree)      
       )
      )
     )
   )
   ((> e (node tree)) 
    (make-tree (node tree) (left-branch tree) (delete e (right-branch tree)) )
   )
   ((< e (node tree)) 
    (make-tree (node tree) (delete e (left-branch tree)) (right-branch tree)  )
   )
  )

  
 )


)


;function for sorting..
(define (sort-tree tree)
 (if (null? tree)
  '()
  (append (sort-tree (left-branch tree)) (list (node tree)) (sort-tree (right-branch tree)))
 )

)

(define (tree-sort set)
 (sort-tree (set->tree set))
)

(define mylist (list 7 4 9 1 2 10 11 15 5))
(define mytree (set->tree mylist))
;mytree