2
$\begingroup$

An algorithm is requested to calculate all balanced binary trees which can be built with $N$ nodes, having exactly $L$ leaves. A balanced tree is a binary tree in which the difference between the heights of the left and right subtrees is at most 1, and the subtrees are themselves balanced.

I tried to use dynamic programming to calculate the number for the subtrees created from any subsequence of $1..N$. However, without building each possible subtree and calculating its height and differentiating the height of the subtrees from each other, it can't distinguish the balanced subtrees. Moreover, the sum of their leaves must be exactly $L$. There are many constraints, and I couldn't come up an algorithm, either a working nor an optimum one.

Could you please guide me?

Source: Assignment of Advanced Algorithms, Fall 2018, Tehran University

Improve this question
$\endgroup$
5
  • $\begingroup$ Just an encouragement here: try harder to deal with all the parameters of a subtee, which includes the number of nodes, the number of leaves, the height. List all the requirements. Check the smaller cases such as 3 or 4 or 5 nodes. $\endgroup$
    – John L.
    Oct 26, 2018 at 12:43
  • $\begingroup$ Here is the subproblem. Compute the number of balanced trees with $N$ node, $L$ leaves and height $H$. Adding $H$ as a parameter makes the subproblem strong enough to go from smaller subproblems to a larger subproblem. This is the golden rule of DP: When you cannot make a recurrence relation because of some missing condition, add a parameter to represent that condition! (I didn't see people call it the golden rule; but that is how I teach my local students.) $\endgroup$
    – John L.
    Oct 26, 2018 at 19:04
  • $\begingroup$ It seems one makes the problem more difficult by adding another parameter. However, that is only way to make it possible to go from smaller subproblems to a larger subproblem. $\endgroup$
    – John L.
    Oct 26, 2018 at 19:07
  • $\begingroup$ @Apass.Jack Thank you, in fact the last time I told you that $t(N,L)$ doesn't give me the heights of trees, I thought that I can add $H$. Now you said the same, I give it another try. $\endgroup$
    – Ahmad
    Oct 26, 2018 at 20:28
  • $\begingroup$ @Apass.Jack I wrote an algorithm and it works! However, I will post it after I delivered the assignment (because of possible copying). $\endgroup$
    – Ahmad
    Oct 26, 2018 at 22:40

1 Answer 1

Reset to default
2
$\begingroup$

Suppose $BTC[H][N][L]$ shows the number of balanced trees with the height $H$, with $N$ nodes and $L$ leaves. Using the following formula, a dynamic programming algorithm can be developed for the problem:

The recursive part: $\begin{align*} BTC[H][N][L] = \sum_{h=0}^H\sum_{n=0}^N\sum_{l=0}^L \qquad&(BTC[h-1][n][l]\times BTC[h-1][N-n][L-l])\\ +&(BTC[h-1][n][l]\times BTC[h-2][N-n][L-l])\\ +&(BTC[h-2][n][l]\times BTC[h-1][N-n][L-l]) \end{align*}$

The base cases: $BTC[h][n][l]=\begin{cases}0 & \text{if $h>\log_2n$ or $l>\frac{n}{2}$ or $n=0$ or $l=0$}\\ 1 & \text{if $h=0$}\end{cases}$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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