Recursive toString() method in a binary search tree. What is the time complexity for this?

The easiest answer is: O(n) You visit every node once and do one (a) amount of work. The calculation would go like.

The easiest answer is: O(n). You visit every node once and do one (a) amount of work. The calculation would go like O(a*n) and because we ignore constant factors, the simple answer would be O(n) But.

One could also argue, your doing just a little bit more: you return null each time you visit a place where there is no leaf. This again is one (b) amount of work to be done. Let's call those invisible leaves for a moment.

Following this idea, every value in the tree is a node which has one or two invisible leafs. So now, we have the following to do (for each node): a | if a node has two child nodes a + be | if a node has one child node a + 2b | if a node has no child node. For a worst case binary tree (totally unbalanced), we have (n-1) nodes with one child node and one node with no child node: "1" \ "2" \ "3" \ "4" And so, the calculation is (n-1)*(a+b) + be an + bn - a - be + be n(a+b) + be => O(an + bn) // we ignore `+ b` because we always look at really big n's Fortunately, even in a worst case time scenario, complexity is still linear.

Only the constant is higher than in the easy answer. In most cases - usually when Big-O is needed to compare algorithms - we even ignore the factor and we're happy to say, that the algorithms time complexity is linear (O(n)).

Fantastic answer! Thank you very much. – MarPet Feb 18 at 8:00.

The time complexity is O(n) since you are visiting every node once. You cannot do any better than that in order walk the tree.

Time complexity is linear in the number of nodes in the tree: you are visiting each node exactly once.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.