The Tree-o-Matic Software company specializes in all things related to trees. Yo

Question

The Tree-o-Matic Software company specializes in all things related to trees. You have been asked to design a new utility class to verify whether a given tree-based array is a Binary Search Tree.

Assignment:

Create a BSTChecker class with the following capabilities:

Feature

Signature

Requirement

Constructors

N/A

A utility class—no constructor needed

Methods

static boolean isValid(Integer [] intArray)

Returns true if array is a valid binary search tree.

Preconditions:

throws NullPointerException if intArray is null. Note: must be explicitly thrown.

Implementation does not need to be recursive.

Feature

Signature

Requirement

Constructors

N/A

A utility class—no constructor needed

Methods

static boolean isValid(Integer [] intArray)

Returns true if array is a valid binary search tree.

Preconditions:

throws NullPointerException if intArray is null. Note: must be explicitly thrown.

Implementation does not need to be recursive.

Explanation / Answer

here is your program : ------------>>>>>>>>>

public class BSTChecker{
public static boolean isValid(Integer[] array) throws NullPointerException{
  if(array == null){
   throw new NullPointerException("array reference is null");
  }
  int left = -1;
  int right = -1;
  int parent = -1;
  for(int i = 0;i<array.length;i++){
   left = (i+1)*2;
   right = (i+1)*2 + 1;
   if(left-1 < array.length)
    if(array[left-1] != null)
     if(array[left-1].compareTo(array[i]) >= 0){
      return false;
     }
   if(right-1 < array.length)
    if(array[right-1] != null)
     if(array[right-1].compareTo(array[i]) <= 0){
      return false;
     }
   if((i+1)%2 == 0){
    parent = (i+1)/2;
    if(right-1 < array.length)
     if(array[right-1] != null)
      if(parent > 0)
       if(array[parent-1].compareTo(array[right-1]) <= 0)
        return false;
   }
   if((i+1)%2 != 0){
    parent = i/2;
    if(left-1 <array.length)
     if(array[left-1] != null)
      if(parent > 0)
       if(array[parent-1].compareTo(array[left-1]) >= 0)
        return false;
   }
  }

  return true;
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.