MCX2                                                                                                             Mr. Stanley Teitel, Principal
Mr. Gary Jaye                                                                                                  Mr. Danny Jaye, Math Chair

                   1996 APCS AB Exam: Question 3

Assume that binary trees are implemented using the following declaration 

  public class  TreeNode {
     public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight) {...}
    public Object getValue() {...}
    public TreeNode getLeft() {...}
    public TreeNode getRight() {...}
    public void setValue(Object theNewValue) {...}
    public void setLeft(TreeNode theNewLeft) {...}
    public void setRight(TreeNode theNewRight) {...}
    < private data members >
}

Part A
Write the function ValsLess whose header is given below. Parameter T refers to a binary tree of Integer objects. 
ValsLess returns true if T is null or if the values of all the Integers pointed to by T are less than k; otherwise ValsLess returns false. 
intValue is the only Integer method needed to implement ValsLess .

Complete ValsLess below the following header.  

   public static boolean  ValsLess(TreeNode T,  int k)
   //  precondition:  T is empty or a binary tree of Integer objects. intValue is the only Integer method needed.
   // postcondition: returns true if T is null or if all values stored in tree represented
   //     by T are less than k; otherwise returns false

Part B
Recall that a binary tree T is a search tree that contains no duplicate values if and only if 

   1. T is empty or 
   2. All of the following are true 
          The value stored at the root of T is greater than all of the values stored in T's left subtree. 
          The value stored at the root of T is less than all of the values stored in T's right subtree. 
          T's left subtree is a binary search tree that contains no duplicate values. 
          T's right subtree is a binary search tree that contains no duplicate values. 

Write function IsBST whose header is given below. IsBST should return true if the binary tree represented by 
 its parameter T is a binary search tree that contains no duplicate values; otherwise IsBST should return false. 

In writing IsBST you may include calls to function ValsLess from part (A). Assume that ValsLess works as 
specified, regardless of what you wrote in part (A). You may also include calls to function ValsGreater whose 
specification is given below. (You do not need to write the body of ValsGreater.) 

   public static boolean  ValsGreater(TreeNode T,  int k) 
   // postcondition: returns true if T is null or if all values stored in tree represented
   //     by T are greater than k; otherwise returns false

intValue is the only Integer method needed to implement IsBST. Complete function IsBST below the following header. 

   public static boolean IsBST(TreeNode T) {
   //  precondition:  T is empty or a binary tree of Integer objects. intValue is the only Integer method needed. 
   // postcondition: returns true if T represents a binary search tree containing no duplicate values; otherwise, returns false.