# How to solve recurrence of a binary tree

I'm trying to solve this recurrence of a function of a binary tree with a recursive tree. But I can't find any pattern to solve it.

This function calculates both the height and if its a balanced tree.

template <typename T>
std::pair<bool, int> balanced_height(const BinTree<T> &tree) {
if (tree.empty()) {
return {true, 0};
} else {
auto [bal_left, height_left] = balanced_height(tree.left());
auto [bal_right, height_right] = balanced_height(tree.right());
bool balanced = bal_left && bal_right && abs(height_left - height_right) <= 1;
int height = 1 + std::max(height_left, height_right);
return {balanced, height};
}
}

And the recurrence, $$n$$ is the number of tree nodes. I think that $$n_l$$ and $$n_r$$ should decrease in each call by 1.

$$T(n) = \begin{cases} T(n_l)+T(n_r) + 1 & \text{if } n \gt 0, \\ 1 & n = 0 \\ \end{cases} \\ \text{Given that }n_l+n_r+1=n$$

• You cannot solve this recurrence since it’s not completely specified. – Yuval Filmus Apr 3 at 4:47
• The heights do not satisfy the equation $n_l + n_r + 1 = n$. Rather, $n = \max(n_l,n_r) + 1$. – Yuval Filmus Apr 3 at 9:17
• @YuvalFilmus They just gave me that recurrence in the lecture, but now that I think about it, it doesn't seem right, I have updated the question with the code, what would be the correct recurrence for that, and how can I solve it. Sorry I'm a bit newbie with maths. – Tiberius Apr 3 at 11:33

There are several slightly different ways of defining binary trees. You seem to be using the following: a binary tree is either a leaf, or an ordered pair of binary trees.

Your recursive procedure actually computes two different functions: the first output is a Boolean function $$b$$ which measures whether the tree is balanced, and the second is an integer-valued function $$h$$ which computes the height of the tree.

The height function $$h$$ is defined as follows: if $$T$$ is a leaf then $$h(T) = 0$$, and if $$T = (T_\ell,T_r)$$ then $$h(T) = 1 + \max(h(T_\ell),h(T_r))$$. This function computes the height of the tree.

The balancedness function $$b$$ is defined as follows: if $$T$$ is a leaf then $$b(T) = \mathsf{true}$$, and if $$T = (T_\ell,T_r)$$ then $$b(T) = b(T_\ell) \land b(T_r) \land |h(T_\ell) - h(T_r)| \leq 1$$. In words, a tree is balanced if in every internal note $$v$$, the heights of the left and right subtrees differ by at most one.

As you can see, the argument of both functions is a tree.

Your recurrence describes the worst-case running time of the procedure as a function of the number of nodes. The base case is $$T(1) = O(1)$$ (when the tree is a leaf), and when $$n > 1$$, $$T(n) = \max_{\substack{n_\ell,n_r \geq 1 \\ n_\ell+n_r+1=n}} T(n_\ell) + T(n_r) + O(1).$$ The solution is $$T(n) = \Theta(n)$$. You can prove this by induction. In particular, if you replace $$O(1)$$ by $$1$$, a simple induction shows that $$T(n) = n$$.

In fact, it is not hard to check that your procedure has running time $$\Theta(n)$$ on any tree having $$n$$ nodes, since the recursive calls "visit" every node in the tree, and do $$O(1)$$ processing per node.

• Then, what would be the correct recurrence and the asymptotic cost of the function? – Tiberius Apr 3 at 12:38
• Assuming that you're interested in worst-case running time, you need to add a $\max$ in the appropriate place. In fact, in this particular case, the running time truly only depends on the number of nodes, but this isn't always the case. – Yuval Filmus Apr 3 at 13:13