Timeline for Printing a K-ary tree stored in level-order in an array
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 4, 2018 at 3:08 | comment | added | Prithvi Boinpally | I see. That makes sense, and it handles the edge case well. Thank you so much | |
| Nov 4, 2018 at 2:39 | comment | added | 200_success |
Math.min() says to proceed to the end of that row, but keeping in mind that the bottom row might be incomplete.
|
|
| Nov 3, 2018 at 23:35 | comment | added | Prithvi Boinpally | Oh i get it now. And yeah I realized that the extra space was being added so I just added a space to the first index to compensate. Your solution is much better though. And one last thing, could you explain what the math.min is doing? I'm a bit confused by how you are finding that the iteration has reached the next level of the tree. | |
| Nov 3, 2018 at 22:53 | comment | added | 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.)
|
|
| Nov 3, 2018 at 22:50 | comment | added | Prithvi Boinpally | I am a little confused though, what exactly is your ternary checking? Is that a nested ternary? | |
| Nov 3, 2018 at 22:43 | vote | accept | Prithvi Boinpally | ||
| Nov 3, 2018 at 22:41 | comment | added | 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). | |
| Nov 3, 2018 at 22:39 | comment | added | 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.
|
|
| Nov 3, 2018 at 22:37 | comment | added | 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). | |
| Nov 3, 2018 at 22:32 | history | answered | 200_success | CC BY-SA 4.0 |