0
$\begingroup$

I have this function which traverses each node of a left child-right sibling binary tree once and I want to solve the recurrence relation of the function.

First of all I think the relation looks like this:
T(n) = 1+m[4+T(n-m)] = 1+4m+mT(n-m)

Where m is the number of nodes on a level and n the total amount of nodes in the tree.

Is this correct? And how could I solve this recurrence relation with two variables?

void maxWidth(Node node, int height, vector<int> &width){
    if(node==nullptr){
        return;
    }
    while(node!=nullptr){
        if(width.size()==height){
            width.push_back(0);
        }
        if(width.size()>height){
            width[height]=width[height]+1;
        }
        if(node->left_child!=nullptr){
            maxWidth(node->left_child,height+1,width);
        }
        node=node->right_sib;
    }
}
$\endgroup$

1 Answer 1

0
$\begingroup$

If you insist on solving a recurrence formula, you might want to compute $T$ based on the height of the tree first. Computing $T$ based on the number of nodes is much more complicated, and the $T(n-m)$ there is not correct - it needs to be $T(n-\sum_{i=1}^m{k_i})$ where $k_i$ is the size of the sub-tree which is rooted in the $i$'th child.

Otherwise (which is what I recommend doing), just notice that you will visit each node at most once. In each visit you will pay no more than $O(1)$ before each recursive call, and hence this algorithm will total to be $O(n)$.

However the above reasoning will need to be formalized if you want to keep it as a proof. That is, you will have to prove that indeed you will not visit each node more than once.

$\endgroup$
4
  • $\begingroup$ I knew it was O(n) but I didn't know how to prove it, thanks for pointing out that T(n-m) was wrong in the formula $\endgroup$ Dec 14, 2021 at 11:43
  • $\begingroup$ If you would have kept it, the result would have been enormous, something like $\Omega(m^{\frac{n}{m}})$ $\endgroup$
    – nir shahar
    Dec 14, 2021 at 12:16
  • $\begingroup$ how would you compute T using the height of the tree? $\endgroup$ Dec 14, 2021 at 13:54
  • $\begingroup$ Assuming the tree is balanced, $T(h)=O(m)+mT(h-1)$. If I'm not mistaken, solving this yields $T(h)=O(\sum_{i=1}^h m^i)=O(\sum_{i=1}^\log_m(n) m^i)=O(m^{\log_m(n)})=O(n)$ $\endgroup$
    – nir shahar
    Dec 14, 2021 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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