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
Binary Search Tree (BST)
All nodes in the left sub-tree of any node with
value K have values <= K and all nodes in the
right sub-tree have values greater than K.
AVL Tree
A binary search tree in which the heights of
left and right sub-trees at every node differ
by at most 1.
Final Output
4 2 1 3 6 5 7
