Given the pre-order traversal, we can easily obtain the necessary Binary Search Tree(BST- not necessarily balanced). However, the problem arises when we have to decide the balancing manually(this was a question in a written quiz). Is it possible to do so in any way?

Edit: I built the BST following the steps in this video: https://www.youtube.com/watch?v=rOiqrg5AH7M. After this step, I proceeding on to balancing the tree following zig-zig and zig-zag rotation(all four possible cases). However, the resulting tree did not have the same preorder traversal.(I unfortunately don't have access to the exact values given in the question, neither to my answer).

My doubt is: how do I obtain the correct AVL tree?

  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you and future readers understand the concepts. It is expected of you to show your partial progress, thoughts or where you got stuck. It will help draw more better answers faster. This site is a knowledge-sharing question-and-answer place instead of a solution rendering service. $\endgroup$ – John L. Apr 2 '19 at 17:36
  • $\begingroup$ Yes, of course @Apass Jack. Thank you for your advice. $\endgroup$ – Shubhayu Apr 3 '19 at 13:43
  • $\begingroup$ Can you give one example with the complete input and the expected output? My concern is, do we know the in-order traversal? That is, is the total order of the elements known? $\endgroup$ – John L. Apr 3 '19 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.