Question4, 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

Lisp ft Jaxon

(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))
                 (print "This is a valid binary tree")
                 (print "This is not a valid binary tree")
        ))
         
         
         ; Case 2: 1 left, 0 right (and (not (= leftChild () )) (= rightChild () ) ) 
        
           (if  (and (not (eq leftChild () ))  (eq rightChild () ))
                (if (or (> root leftChildNode) (= root leftChildNode)) 
                (print "This is a valid binary tree")
                (print "This is not a valid binary tree")
        ))

; Case 3: 0 left, 1 right (and (= leftChild () )) (not (= rightChild () ) ))
         (if (and (eq leftChild () ) (not (eq rightChild () )))
         (if (< root rightChildNode)
            (print "This is a valid binary tree")
            (print "This is not a valid binary tree") 
        ))
         
         ;Case 4: 0 left, 0 right 
         (if (and (eq leftChild () ) (eq rightChild () ))
         (print "This is a valid binary tree"))))))))
        
    
(isValid '(5 (4 () ()) (85 () ())))

;(defun BST (tree)

;(BST '(8 (3 (1 () ()) (6 (4 () ())(7 () ()))) (10 () (14 (13 () () ) ()))))

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