How to solve recurrence of a binary tree

Question

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

Answer 1

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.