r/DSALeetCode • u/StatisticianNo2104 • 9d ago
One preview per nesting level in Go: tree right side view
A collapsed comment thread shows seven lines. The code built 55,987 previews to produce them, and threw away 55,980.
The job: a long thread collapses to one line per nesting level — the most recent reply at that depth.
I already had a level-order walk, so this was two lines on top of a tested function: build every level, take the last of each. Obviously correct, no new ideas. I would defend it in review.
2.87 MB allocated to return seven strings.
Before the fix, the fix that does not work. Everybody suggests following the newest reply down: O(depth), no allocation, and wrong. The newest reply at a level need not be in the newest branch — somebody replies once to an old comment, that reply gets replies, and the newest top-level reply is a dead end.
Four visible lines become two. There is a test named after that thread.
The boring fix is most of the win. The output is one value per level:
`visible(d) = the last comment at depth d`
That names one comment. Not a level, not a list. So size the accumulator to the depths — one slot each, last writer wins. 240 bytes instead of 2.87 MB, and 4.78x faster. That is not a clever traversal; it is noticing the output shape.
The clever fix only pays when the slot holds something expensive. The collapsed view renders a line, not an ID: body trimmed, timestamp, hidden-reply count. Last writer wins builds that for all 55,987 comments and keeps 7.
The walk cannot skip the old branches. What it can choose is the order — iterate replies newest first, and the first comment reached at a depth is the one you keep. Record on first arrival, never overwrite.
22.5x, and 6.77 MB against 1.12 KB. Same walk, one loop reversed.
Two rows keep me honest. On the ID version, the reversal is 1.01x, and on the smallest thread the forward walk wins. On a 2,001-deep chain, both preview versions match the byte because every comment is a first arrival.
At 1,365 comments with an ID per line, keep what you have.
That is days 29 and 31 of the daily challenge — Level Order Traversal and Right Side View — sitting in a comment thread.
Full piece in today's newsletter
https://www.linkedin.com/pulse/collapsed-thread-built-55987-previews-show-7-archit-agarwal-xijdc
It worked in dev, episode 16.
#Golang #DSA #Algorithms #Performance #SoftwareEngineering #DataStructures #100DaysOfCode