Description

Problem Description:
Write a program that takes a sequence of integers as input, constructs a binary tree and checks whether the tree is an AVL tree or not. The input consists of a sequence of different integers. Construct a BST by inserting the nodes into their correct place. After inserting all integers into the binary search tree check if the final tree is AVL or not. If the tree is AVL print the preorder traversal of the tree. Otherwise, Print “NOT” in the output. You can assume the sequence comprises of unique numbers. There are no equal integers for each input line.

Input:
The input has only one line consisting of the integers that should be inserted in the binary search tree. -1 signals the end of the input.
Output:
The output also has only one line which is the preorder traversal of the tree if it is AVL or the word “NOT” if the tree is not AVL.

SR Input Output
1 4 2 6 3 5 7 1 -1 4 2 1 3 6 5 7
2 7 5 8 3 12 23 9 27 55 33 2 -1 NOT
3 5 2 12 1 3 9 17 15 19 -1 5 2 1 3 12 9 17 15 19