# Finding no. of leaf nodes for each node in a BST

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

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

I am actually looking for a subtle hint.

• That's a basic question, if a nice one. What are your thoughts? Which kind of balance is referenced here? – Raphael Apr 12 '13 at 10:00

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.

• In a binary search tree with $n$ nodes, how many leaves are there?
• How often is each leaf "counted" by $g$?