C++ AVL Tree - How to recover node input order using only preorder and postorder

Question

For my project at university, I am implementing an AVL tree class in C++ with characters for values. We have an autograder which points out our errors with random tests, if present. I ran it multiple times, quite a lot, and got no errors, which means it should have OK logic. However, sometimes I got an error stating that my preorder and postorder traversals are wrong. This is one of the actual errors I got:

YOUR PREORDER: "IECABDGFHPLKOUSRYX", YOUR POSTORDER: "BADCFHGEKOLRSXYUPI" 
CORRECT PREORDER: "ECABDOIGFHKLURPSYX", CORRECT POSTORDER: "BADCFHGLKIPSRXYUOE"

Yes, these trees are still balanced, but somehow incorrectly put together. How should I go about debugging this? I have a function which can reconstruct trees using preorder and postorder, but I think the order of putting variables in matters. Otherwise, I have no way of knowing the order of node input and where my algorithm went wrong.

Answer 1

Consider writing your own test engine, that picks a random string, runs it through your algorithm and gets the preorder it spits out, sorts the random string in preorder and compares the two.

if they don't match, it prints the random string and the two orders. That should help you find failing preorder test cases.

then add post order to the random tester, and run it some more. You might be able to reuse this for future projects.

Google Fuzzer for other ideas :)

Answer 2

Obviously it would be better if, given the test results, you could analyze your code and figure out what is causing the issue.

But it is also sometimes useful to be able to extract more information from a black box system. Here's one approach that may work in your situation.

If you can run code through the autograder multiple times without affecting your grade you get the input for the failing cases using the following method.

Make a dummy routine in your program that will return the test input data in the order it is provided. Then replace you preorder function with this dummy function. Obviously this will fail every test but if you look at only the failures where both the preorder and postorder fail this will give you inputs for the failing postorder.

Repeat this process using the real preorder function and replacing the postorder with the dummy method.