Some Questions have multiple answers. please keep that in mind.

1. Given a binary search tree containing integer values, write an algorithm to count the number of nodes storing values greater than low and less than high. Write your own solution and then compare it with the one below. Select all correct answers. You may assume the following declaration for tree nodes: class TreeNode { public: int x; TreeNode left; TreeNode right; } BST3.jpg

For example, in the tree above, count (t, 9, 20) would yield 7. int count( TreeNode t, int low, int high ){ if(t.x =high) return count(t.left, low, high); return count(t.left, low, high) && count(t.right, low, high); }

Need to add if (t==NULL) return 0;

Needs to count the root if it is between low and high

The direction of the comparisons need to be reversed

Needs to add, if (low==high) return 1

the && needs to be +

2.

Here is another proposed solution to the problem of counting how many nodes are between low and high in a BST. Select all correct answers.

int count(TreeNode t, int low, int high){ if(t == NULL) return 0; int tempInt = 0; tempInt = tempInt + count(t.left, low, high); if(t.value > low && t.value

This produces the correct ansers

This is wrong because tempInt is reset to 0 each time.

This is wrong because you need to check and t.left and t.right are not NULL

This is inefficient as it always traverses the whole tree, even when it doesn't need to.

3.Here is another solution to the problem of counting how many nodes are between low and high. Select all correct answers.

int count( TreeNode t, int low, int high ) {

if (t==NULL) return 0; int leftCount = count(t.left, low, high); int rightCount = count(t.right, low, high);

if(t.x

if(t.x >= high) return leftCount;

return leftCount + rightCount + 1;

}

The last return is missing an if before it.

This produces correct results

This is inefficient as you traverse the whole tree even when you don't need to.

You need another base case.

4.You wrote a recursive routine to determine if the contents of an array are ordered. Your attempt and its output is shown below. Find the error(s) and compare with those below. Select all correct answers.

bool inOrder(int a[], int low, int high) { if (low>high) return true; if (low==high) { return true; } int mid = (high+low)/2; return inOrder(a,low,mid) && inOrder(a,mid+1,high); } void main () {int a[16] = {1,62, 15, 16,17,18,192,21,55,62,63,64,65,67,68,74}; bool okay= inOrder(a,0,15); if (okay) System.out.println ("Is Okay"); else System.out.println ("Not Okay");

Output is: Is Okay

You must replace if (low >high) return true; with if a[low] >a[high] return false

You must add if (a[mid] > a[mid+1]) return false;

the && needs to be ||

mid is computed incorrectly. It needs to be mid=(high-low)/2

This cannot be done recursively

8 7 4