The worst case running time to search for an element in a balanced binary search tree with n2ⁿ elements is

Consider the following program that attempts to locate an element x in a sorted array a[] using binary search. Assume N>1. The program is erroneous. Under what conditions does the program fail?

      var          i,j,k: integer; x: integer;
                   a:= array; [1...N] of integer;
      begin	   i:= 1; j:= N;
      repeat	   k:(i+j) div 2;
                   if a[k] < x then i:= k 
                   else j:= k 
      until (a[k] = x) or (i >= j);
      if (a[k] = x) then
      writeln ('x is in the array')
      else
      writeln ('x is not in the array')
      end; 

A binary search tree is used to locate the number 43. Which of the following probe sequences are possible and which are not? Explain.

(a) In a binary tree, a nil node is defined to be a node with 2 children. Use induction on the height of the binary tree to prove that the number of full nodes plus one is equal to the number of leaves.

(b) Draw a min-heap that results from insertion of the following elements in order into an initially empty min-heap: 7, 6, 5, 4, 2, 3, 1. Show the result after the deletion of the root of this heap.

(a) Insert the following keys one by one into a binary search tree in the order specified.

         15, 32, 20, 9, 3, 25, 12, 1  

Show the final binary search tree after the insertions.
(b) Draw the binary search tree after deleting 15 from it.
(c) Complete the statements S1, S2 and S3 in the following function so that the function computes the depth of a binary rooted at t.

              typedef struct tnode{
                  int key;
                  struct tnode *left, *right;
              } *Tree;
              int depth(Tree t)
              {
                  int x,y;
                  it (t == NULL) return0;
                  x=depth(t → left);
 S1:              ____________;
 S2:              if(x>y) return _____________:
 S3:              else return _____________;
              } 

Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

Let T(n) be the number of different binary search trees on n distinct elements. Then , where x is

The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

Suppose we have a balanced binary search tree T holding n numbers.  We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(n^alog^bn + m^clog^dn), the value of a + 10b + 100c + 1000d is ____.