Objectives
• Workwithtrees
• UseBinarySearchTrees
Activities
Trees
1. WriteaSCHEME functionnamedtree-depthwhichtakesatreenode, n,asaparameterandreturnsthedepth ofthetreerootedat n. Forthepurposeofthisexercise,thedepthofatreerootedat n isoneplusthemaximum ofthedepthsofitstwochildren. Recallthefollowingcodefromthelectureslides: (define (make-tree value left right) (list value left right))
(define (value T) (car T)) (define (right T) (caddr T)) (define (left T) (cadr T))
(define (insert x T) (cond ((null? T) (make-tree x ’() ’())) ((eq? x (value T)) T) ((< x (value T)) (make-tree (value T) (insert x (left T)) (right T))) (( x (value T)) (make-tree (value T) (left T) (insert x (right T))))))
2. Define a SCHEME function named occurences-in-tree which given a binary tree and a value, returns the numberofoccurrencesofthevalueinthetree. 3. Define a SCHEME function named count-one-child which returns the number of internal nodes of a binary treewhichhaveexactlyonechild.
Binary Search Trees
4. DefineaSCHEME functionnamed(invert-bst T)which,givenaBinarySearchTree(BST)invertsthatBST. That is, the function returns a binary tree in which has the property that all values at nodes in the left subtree are greater than the value at the root node and all values at nodes in the right subtree are less than the value at therootnode. 5. WriteaSCHEME functionwhich,givenabinarysearchtreeT andaninteger z,returnsthenumberofintegers inthetreethataregreaterthanorequaltoz. Forexample,giventhetreebelowandthenumber5,yourfunction shouldreturn4,sincethereare4numbersinthetreethataregreaterthanorequalto5(specifically,5,8,11,and 21).
1
Yoursolutionshouldexploitthefactthatthetreeisabinarysearchtreetoavoidconsideringcertainsubtrees.
8
11
21
4
1 5
Figure1: Abinarysearchtreewith6nodes,4ofwhichare5orlarger.
