Concatenation tree
= Concatenation tree
A <tree> representation of a <list> with empty nodes, single-element nodes and binary concatenation nodes. Concatenation constructs one node without traversing either operand. The representation need not be unique: adding empty branches changes its size without changing the denoted <list>. An accumulator-based traversal gives <linear flattening of a binary tree> in the representation's size rather than merely the output length.