edited by
31,431 views
103 votes
103 votes

A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is: $$\Large \min \left ( \substack{\text{number of leaf-nodes}\\\text{in left-subtree of $x$}}\;,\; \substack{\text{number of leaf-nodes}\\\text{in right-subtree of $x$}}\right )$$

Then the worst-case time complexity of the program is?

  1. $\Theta (n)$
  2. $\Theta (n \log n)$
  3. $\Theta(n^2)$
  4. $\Theta (n^2\log n)$
edited by

11 Answers

8 votes
8 votes

The actual question which is asked is different than what we people understood

7 votes
7 votes

Height of balanced binary search tree = logn

So there are logn levels in tree

At one node we need to find left and right sub tree leaves

The recurrence relation will be T(n) = left sub tree + right sub tree + root

T(n) = T(n/2)+T(n/2)+1 = 2T(n/2) + 1 = O(n)

There are logn levels so T(n) = O(nlogn)

3 votes
3 votes

Traversing BST gives O(log n) and we have to compute MIN on "n" nodes so O(n), So finally O(n)*O(log n) = O(n log n).

3 votes
3 votes
The recurrence relation for the recursive function is
T(N) = 2 * T(N/2) + n/2
Where N is the total no. of nodes in the tree.
T(N) = 2 * (2*T(N/2) + n/2) + n/2
     = 4 * T(N/2) + 3(n/2)
Solve this till T(1) i.e. till we reach the root.
T(N) = c * T(N / 2^i) + (2*i - 1) * (n/2)
Where i = lg(N)
= lg((2n - 1) / 2)
O(c * T(N / 2^i) + (2*i - 1) * (n/2)) reduces to
O((2*i - 1) * (n/2))
O((2*( lg((2n - 1) / 2)) - 1) * (n/2)) ...sub the value of i.
O(n * ln(n)) 
Answer:

Related questions

27 votes
27 votes
6 answers
1
Kathleen asked Sep 18, 2014
22,413 views
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 heigh...
62 votes
62 votes
4 answers
3
55 votes
55 votes
8 answers
4