A program takes as input a balanced binary search tree with n leaf nodes and…
GATE · 2004 · CS
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
- A.
Θ(n)
- B.
Θ(nLogn)
- C.
Θ(n2)
- D.
Θ(n2log n)
Attempted by 428 students.
Sign up free to check your answer
Sign up freeLoading lesson…