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
$\qquad \min(\#\text{leaves in } L(x), \#\text{leaves in } R(x))$
for $L(x), R(x)$ the left resp. right subtree of $x$, then the worst-case time complexity of the program is
I am actually looking for a subtle hint.
Traverse your graph in post order, create two auxiliary functions, $Cost$ and $Total$, first one demonstrates cost of your $g(x)$ at each vertex, second one calculates total number of leafs. set the cost function to zero: $Cost(leaf)=0$ for leaf, and $Total(leaf) = 1$ for leaf, then for parent node set this two functions as:
$$Cost(v) = min\{Total(child_l),Total(child_r)\}$$$$Total(v) = Total(child_l) + Total(child_r)$$
Because is post order, will be filled correctly and is $O(n)$ algorithm.
But actually worst case complexity in different algorithm may be differ, you can show that you cannot do this better than $\Omega(n)$, and above algorithm is $\Theta(n)$, which gives a tight bound, but, may be someone implement it in a bad way that causes to the $\Omega(n^9)$, or may be someone else provide an algorithm of $\Theta(n^3)$, At all, I mean your current question is not well defined, and if it was for real exam, it was wrong, and any answer which satisfies $\Omega(n)$ barrier, is correct.
Three questions that can lead you towards an answer:
