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

i'm beginner in java , looking help.

so i've made binary tree in java, , i'm supposed implement method sorts elements in order , convert them string. it's supposed ex. "[1, 2, 3, 4]". used stringbuilder in order this.

my code method looks loke this:

/**  * converts nodes in current tree string. string consists of  * elements, in order.  * complexity: ?  *   * @return string  */ public string tostring() {     stringbuilder string = new stringbuilder("[");     helptostring(root, string);     string.append("]");     return string.tostring(); }  /**  * recursive method tostring.   *   * @param node  * @param string  */ private void helptostring(node<t> node, stringbuilder string) {     if (node == null)         return; // tree empty, leave.      if (node.left != null) {         helptostring(node.left, string);         string.append(", ");     }      string.append(node.data);      if (node.right != null) {         string.append(", ");         helptostring(node.right, string);     } } 

so question is, how calculate time complexity this? also, if there suggestions in how make method better, gladly appreciate it.

the easiest answer is: o(n). visit every node once , 1 (a) amount of work. calculation go like

o(a*n) 

and because ignore constant factors, simple answer be

o(n) 

but. 1 argue, doing little bit more: return null each time visit place there no leaf. again 1 (b) amount of work done.

let's call invisible leaves moment. following idea, every value in tree node has 1 or 2 invisible leafs.

so now, have following (for each node):

a       | if node has 2 child nodes + b   | if node has 1 child node + 2b  | if node has no child node. 

for worst case binary tree (totally unbalanced), have (n-1) nodes 1 child node , 1 node no child node:

  "1"     \     "2"       \       "3"         \         "4" 

and so, calculation is

     (n-1)*(a+b) + b  <=> + bn - - b + b  <=> n(a+b) + b    => o(an + bn)  // ignore `+ b` because @ big n's 

fortunately, in worst case time scenario, complexity still linear. constant higher in easy answer. in cases - when big-o needed compare algorithms - ignore factor , we're happy say, algorithms time complexity linear (o(n)).