Dynamic Programming algorithm

A binary tree T is semi-balanced if for every node m in T:

R(m)/2 <= L(m) <= 2*R(m),

where L(m) is the number of nodes in the left-sub-tree of m and R(m) is the number of nodes in the right-sub-tree of m.

(a) Write a recurrence relation to count the number of semi-balanced binary trees with N nodes.

(b) Provide a Dynamic Programming algorithm for computing the recurrence in (a).

How do i go about making the recurrence relation for this?

Does the following qualify?

if(node==NULL)
return;
if(given relation is true)
count++
else find for right tree;
     find for left tree;

I guess he is asking more of a recurrence relation like a function or something.?

Also how do i go about doing the problem using dynamic programming? I guess i dont need to store anything if i apply the above suggested code snippet.

Kindly help.

Answers


Hint: Let C(n) be number of semi-balanced trees with n nodes. If you know values for C(1), C(2), ..., C(n) than it is easy to calculate C(n+1) by taking root node and dividing remaining n nodes into left and right sub-trees by condition stated.

Number of nodes in sub-trees can be from n/3 to 2*n/3, since these values satisfy condition R(n)/2 <= L(n) <= 2*R(n).


Need Your Help

Editable Bootstrap Table “Jumping”

jquery twitter-bootstrap table

I have made a table with Bootstrap classes editable by double clicking on a cell. However the cell width automatically grows and makes other columns "jump" which can be annoying.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.