Search code examples
binary-treedynamic-programmingrecurrence

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.

Solution

  • 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).

    Update:

    C(n) = sum from n/3 to 2n/3 L(n)*R(n)