The difference is run from end to 0 instead of run from 0 to end.
In additional, we should contruct the right tree before the left one.
Pre-order: A, C, E, D, B, H, I, G, F
<- p
In-order: A, B, C, D, E, F, G, H, I
q