GATE CSE 2004 | Question: 85

Question

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?

• A. $\Theta (n)$
• B. $\Theta (n \log n)$
• C. $\Theta(n^2)$
• D. $\Theta (n^2\log n)$

Comments

poor basics in a subject often give headaches.

This question follows basic equation

 

N(h)>=N(h-1) + N(h-2)

N(h)>= 2N(h-2)

height is always log(n)

for each node u do this

for n leaf nodes, max time u will need it nlogn

---

@ Bikram

“we first need to count no. of leaf in left sub-tree, then no. of leaf in right sub-tree + compare them to find minimum”

Here when we see the recurrence relation that you proposed, how are we sure that there will be exactly n/2 leaf nodes in both left sub-tree and right sub-tree? like there can be n/3 leaf nodes in left sub-tree and 2n/3 leaf nodes in right sub-tree.

I hope you got my doubt!

---

https://gateoverflow.in/1079/gate-cse-2004-question-85?show=379216#a379216

this answer by User-Jiren is must read, @Sachin Mittal 1 sir gave some really nice insights there

Answer 1

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

Answer 2

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)

Answer 3

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).

Answer 4

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)) 

Comments

Sir i think answer should be O(n)

because this this same like build max  heap

aprox we have 2n node

we take array of 2n elements and start from end

to compute and when computing for second last node use last node g(x) values so at each node only constant time

n*(constant)+N/2(Constant).......................+1==O(n)

last level        second Last Level.................Root node

---

Sir I don't get why u added n/2 in the recurrence relation. If I make the lower nodes pass the no. of leaves to it's parent besides calculating g(x) for itself, parent just has to find min out of two. so T(n)=2*T(n/2)+c & I'll get O(n). What's wrong in the following approach:

base case when node is a leaf node- g(x)=0 & pass 0 to it's parent

Let a node get n1, n2 from it's left, right subtrees. Calculate g(x) for itself but pass n1+n2 to it's parent. In case any one of n1, n2 is 0 then pass n1+n2+1. If both are 0s pass n1+n2+2.