C# Algorithms Online Test

Binary search tree (BST) is a binary tree where the value of each node is larger or equal to the values in all the nodes in that node's left subtree and is smaller than the values in all the nodes in that node's right subtree.

Write a function that, efficiently with respect to time used, checks if a given binary search tree contains a given value.

For example, for the following tree:

• n1 (Value: 1, Left: null, Right: null)
• n2 (Value: 2, Left: n1, Right: n3)
• n3 (Value: 3, Left: null, Right: null)

Call to Contains(n2, 3) should return true since a tree with root at n2 contains number 3.

Write a function that, when passed a list and a target sum, returns, efficiently with respect to time used, two distinct zero-based indices of any two of the numbers, whose sum is equal to the target sum. If there are no two numbers, the function should return null.

For example, FindTwoSum(new List<int>() { 3, 1, 5, 7, 5, 9 }, 10) should return a Tuple<int, int> containing any of the following pairs of indices:

• 0 and 3 (or 3 and 0) as 3 + 7 = 10
• 1 and 5 (or 5 and 1) as 1 + 9 = 10
• 2 and 4 (or 4 and 2) as 5 + 5 = 10

Implement function CountNumbers that accepts a sorted array of unique integers and, efficiently with respect to time used, counts the number of array elements that are less than the parameter lessThan.

For example, SortedSearch.CountNumbers(new int[] { 1, 3, 5, 7 }, 4) should return 2 because there are two array elements less than 4.