Constructing the sword/fishbone has to be O(n**2) doesn't it? Because you're backfilling all the leaves that are empty in an inner loop? I was trying to do it in O(n) with 3 iterators: left, middle, right, but I couldn't figure it out.