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