now, i know we've had an argument about this before on this thread, but i've looked back at it and i cant understand why i thought it made sense.....
It's to do with the worst case scenario of those tree traversals! I was saying that they weren O(n^2) in the worst case, but camford said they were. We came to the conclusion that the worst case for a pre-order traversal is straight down to the left.
With append an O(n) function where n is the size of the list being appended to, then we have the following:
For a tree going A-B-C-D down the left you first do:
D @ [] @ [] = 1 (since [] @ [] takes no time supposedly)
C @ [D] @ [] = 2 (do the [D]@[] = 1, then the C@[D] = 1)
if you keep going, this appears to be O(n).....so where did the O(n^2) come from?