While the link from w to its parent may point either to the right or left, the optimal layout for w's subtree given that w attaches to its left must be the mirror image of the optimal layout given that w attaches to its right.
only one case need be considered, and the optimal layout for the entire sentence can be computed from the bottom up using just one dynamic programming state for each node in the tree.