# How to write recurrence relation for the following scenario?

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 what is the worst case time complexity?

Since $g(x)$ is applied on the 2 halves of the binary tree, I guess the recurrence relation must look something like :
$$T(n) = 2T\Big(\frac{n}{2}\Big)+k$$
What I could understand from the question is that $g(x)$ is applied on all the $n$ nodes and instead of $k$ it must be something of the order $O(n)$ but I'm not sure what it is. Am I heading in the right direction?

• Why would that be the worst case? Trie to express the true cost as recurrence and estimate that then. Note that "halves" is not right here; most notions of balancedness to not assert that exactly half the number of nodes are in each subtree. In fact, height-balanced trees are per se not even weight-balanced, so the ratio can be arbitrarily bad (AVL, Red-Black).
– Raphael
May 7 '15 at 9:26

If the entire tree has $n$ nodes, what can you say about the number of nodes in the left subtree? What is the smallest it could be? The largest it could be? What about the right subtree?
Imagine you treat the cost of computing $g(x)$ to be measured in dollars, and you charge \$1 to each node in the right/left subtree (whichever is smaller) to account for the cost of computing$g(x)$. For any given node, what can you say about how many dollars it is charged? If you know about amortized analysis, you might review that material. It's not clear to me what$k\$ represents in your proposed approach or where you got that recurrence relation. Why don't you try harder to work out what recurrence relation might be suitable and what its solution is?