 Solution

A concatenation tree may contain arbitrarily many Cat and Nil nodes while denoting an empty or singleton list. For example, repeatedly wrap One x as Cat Nil previous. The output length stays one while the input size grows without bound. An arbitrary leaf could hide another One, so a correct general conversion cannot disregard unexamined branches. Output length alone therefore cannot bound the work; input size must be included.