title: C++ AVL Tree - How to recover node input order using only preorder and postorder
body: <p>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:</p>
  <pre><code>YOUR PREORDER: &quot;IECABDGFHPLKOUSRYX&quot;, YOUR POSTORDER: &quot;BADCFHGEKOLRSXYUPI&quot; 
  CORRECT PREORDER: &quot;ECABDOIGFHKLURPSYX&quot;, CORRECT POSTORDER: &quot;BADCFHGLKIPSRXYUOE&quot;
  </code></pre>
  <p>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.</p>