A program takes as input a balanced binary search tree with n leaf nodes and…
2004
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 min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then the worst-case time complexity of the program is
Answer: B. Θ(nLogn) — We need the total cost: sum over all nodes x of min(number of leaves in left subtree of x, number of leaves in right subtree of x). Count contributions level…
- A.
Θ(n)
- B.
Θ(nLogn)
- C.
Θ(n2)
- D.
Θ(n2log n)
Attempted by 289 students.
Show answer & explanation
Correct answer: B
We need the total cost: sum over all nodes x of min(number of leaves in left subtree of x, number of leaves in right subtree of x).
Count contributions level by level in a balanced binary tree with n leaves.
Let h = log2 n be the height (number of leaf levels). Consider depth d (root at depth 0).
Number of nodes at depth d is 2^d. Each such node has about n / 2^d leaves in its subtree, so min(left, right) ≈ n / 2^{d+1}.
Total contribution from depth d: 2^d * (n / 2^{d+1}) = n / 2, which is Θ(n).
There are h = Θ(log n) levels with internal nodes, so summing over depths 0..h-1 gives total cost = (n/2) * h = Θ(n log n).
Answer: Θ(n log n)
Explore the full course: Iocl Engineers Officers Grade A Paper 2