Printing a K-ary tree stored in level-order in an array

Question

I am given an array that represents a k-ary tree (I am also given the branching factor "k") that is stored in level order. My task was to print the tree in level order.

For example a trinary tree stored as {0,1,2,3,null,null,null,7,8,9,10,11,12} (It doesn't have to be full or complete) would print out as:

0
1 2 3
null null null 7 8 9 10 11 12

My solution currently works fine but it is very messy and not as elegant as I would prefer. The runtime complexity is also very bad (I don't know if Math.pow is O(1) or O(n) but if it's O(1), my code is still O(n) which is not ideal. If Math.pow is O(n) then my code is O(n²) which is garbage.

Is there another approach I am not seeing or can my existing code be optimized at all?

public static void main(String[] args) {
 int k = 3;
 Integer[] arrInt = {0,1,2,3,null,null,null,7,8,9,10,11,12};
 String ans = arrInt[0] + "\n";
 int currLvl = 1;
 int prevLvl = 0;
 //Print all values
 for(int i = 1; i < arrInt.length-1; ++i){
 //Add a line if we reach a new level
 if(i == (Math.pow(k, currLvl)+Math.pow(k, prevLvl))){
 currLvl++;
 prevLvl++;
 ans+= "\n"; 
 }
 ans+= " " + arrInt[i];
 }
 //EDGE CASE TO HANDLE LAST ELEMENT
 ans+= " " + arrInt[arrInt.length-1];
 System.out.println(ans);
}

Answer 1

Your biggest performance problem is the repeated string concatenation using the + operator. Since Java strings are immutable, every += operation requires allocating a new string and copying the previous contents. Use a StringBuilder instead.

Math.pow() should be avoided, since it performs floating-point arithmetic, and this task should be accomplished using just integer arithmetic. Why not keep track of the desired width of the current row, and use an inner loop to print each row?

public static void main(String[] args) {
 int k = 3;
 Integer[] arrInt = {0,1,2,3,null,null,null,7,8,9,10,11,12};
 StringBuilder ans = new StringBuilder();
 for (int i = 0, width = 1; i < arrInt.length; i += width, width *= k) {
 for (int j = i, end = Math.min(i + width, arrInt.length); j < end; ++j) {
 ans.append((j > i) ? " " : (j > 0) ? "\n" : "")
 .append(arrInt[j]);
 }
 }
 System.out.println(ans);
}

• Prithvi Boinpally: I considered doing this but that means I would be nesting a for loop so I would get O(n^2) complexity. In practice, this may not be that bad but I would prefer to keep it at O(n).
• 200_success: No, your analysis is too simplistic! Despite the nesting, it's still O(n), because it visits every element exactly once. Note that in the outer loop, the i += width means that i skips straight to the next row.
• Prithvi Boinpally: Ah I see! That was my mistake then. Yes that would be a much better approach if the complexity is still O(n).
• Prithvi Boinpally: I am a little confused though, what exactly is your ternary checking? Is that a nested ternary?
• 200_success: Yes, it's a nested ternary that decides what kind of whitespace to insert. It's saying: in most cases, put a space before each entry, but if it's the first entry in a line, put a newline instead, and in the special case of the very first entry, no leading whitespace is needed at all. I could also have written .append((j == 0) ? "" : (j == i) ? "\n" : " "), but that would be less efficient for the common case. (Your original code didn't have that conditional, and thus it puts a space at the beginning of the second and subsequent lines.)