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 $$

  • $\begingroup$ You cannot solve this recurrence since it’s not completely specified. $\endgroup$ Apr 3 at 4:47
  • $\begingroup$ The heights do not satisfy the equation $n_l + n_r + 1 = n$. Rather, $n = \max(n_l,n_r) + 1$. $\endgroup$ Apr 3 at 9:17
  • $\begingroup$ @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. $\endgroup$
    – 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.

  • $\begingroup$ Then, what would be the correct recurrence and the asymptotic cost of the function? $\endgroup$
    – Tiberius
    Apr 3 at 12:38
  • $\begingroup$ 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. $\endgroup$ Apr 3 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.