Question 4 et 5, Common Lisp

Language: Layout:

;QUESTION 4

#|
Write a lisp program to check whether a binary tree is a Binary Search Tree. 
A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties:
􏰃 The left sub-tree of a node has a key less than or equal to its parent node's key.
􏰃 The right sub-tree of a node has a key greater than to its parent node's key.
The list representing the structure of a sample binary tree is given in the following: 
'(8 (3 (1 () ()) (6 (4 () ())(7 () ()))) (10 () (14 (13 () () ) ())))

get root : (car list)
get left sub tree : (car (cdr list))
get right sub tree : (car (cdr (cdr list)))

1 root, 2 children       1 root, 1 right child     1 root, 1 left child      1 root no children
'(5 (5 () ()) (5 () ())) |    '(5 () (5 () ()))    |   '(5 (5 () ()) ())     | (5 () ())
 
(cond (question answer)
			...
			(else answer) ; Optional

(defun validity (switch)
     (if (> switch 0)
              (print "This is not a valid")
              (print "This is valid")
             )
    )

(setq switch '())

(defun isValid (tree)
    (let ((root (car tree)))
    (let ((leftChildNode (car (car (cdr tree)))))
    (let ((rightChildNode (car (car (cdr (cdr tree))))))
    (let ((leftChild (car (cdr tree))))
    (let ((rightChild (car (cdr (cdr tree)))))
         
         ; Case 1: 1 left & 1 right child 
         (if (and (not (eq leftChild () )) (not (eq rightChild () )))
             (if (and (or (> root leftChildNode) (= root leftChildNode)) (< root rightChildNode))
                 (progn
                     (isValid leftChild)
                     (isValid rightChild)
                  )
             (setq switch (append switch '(F)))
              
             )        
        )
         
         ; Case 2: 1 left, 0 right (and (not (= leftChild () )) (= rightChild () ) ) 
        
         (if  (and (not (eq leftChild () ))  (eq rightChild () ))
          (if (or (> root leftChildNode) (= root leftChildNode)) 
             (isValid leftChild)
             (setq switch (append switch '(F)))
          )         
         )
         
         ; Case 3: 0 left, 1 right (and (= leftChild () )) (not (= rightChild () ) ))
         (if (and (eq leftChild () ) (not (eq rightChild () )))
          (if (< root rightChildNode)         
             (isValid rightChild)
             (setq switch (append switch '(F)))
                     
          )
         )
    
         ;Case 4: 0 left, 0 right 
         (if (and (eq leftChild () ) (eq rightChild () ))
             (return-from isValid)
         )
         
         
         )
        )
       )
      )
     )
    (print switch)
    )

(append ((isValid '(8 (3 (1 () ()) (6 (4 () ())(7 () ()))) (10 () (14 (15 () () ) ())))))

#| Question 5
    balancedp(lst)
        create counterRight --> counts the number of elements that are not lists in right side
        create counterLeft --> counts the number of elements that are not lists in left side

if oddp list-length(lst)
            create leftList by cutting lst in half & including the middle element (or ignore it?)
            traverse-and-count(leftList)
            
            create rightList by cutting lst in half & including the middle element (or ignore it?)
            traverse-and-count(rightList)

return (= list-length(leftList) list-length(rightList))
            
        else 
            create leftList by cutting lst in half
            traverse-and-count(leftList)
            
            create rightList
            traverse-and-count(rightList)

return (= list-length(leftList) list-length(rightList))

traverse-and-count(lst)
        traverse lst
                if current element is not a list
                    incr counterLeft
                else
                    repeat traverse-and-count(inner list)
    
    
    
    QUESTION 5

Case 1 No inner lists : is balanced
    Case 2 One inner list: length of inner list = length of list
    Case 3 multiple inner lists

((1 2) (3 1)) 2
(1 2)           2
(3 (1))         2

[ + ] Show input
Absolute running time: 0.19 sec, cpu time: 0.03 sec, memory peak: 6 Mb, absolute service time: 0,33 sec