//DO NOT EDIT ANYTHING IN SOLUTION CLASS
import java.util.*;
class AVLTree
{ // Insert == O(log2N)
Node root;
class Node {
int data, height;
Node left, right;
Node(int v)
{ this.data = v; height = 1; }
}
int height(Node n) {
if( n == null ) return 0;
return n.height;
}
int balanceFactor(Node n){
if(n == null) return 0;
return height(n.left) - height(n.right);
}
void insert(int v) {
root = insert(root, v);
}
Node insert(Node n, int v){
if(n == null) return new Node(v);
if(v < n.data) n.left = insert(n.left, v);
else if(v > n.data) n.right = insert(n.right, v);
else if(v == n.data) return n;
int bf = balanceFactor(n);
n.height = Integer.max(height(n.left), height(n.right))+1;
if(bf < -1){
if( v < n.right.data ) n.right = rightRotate(n.right);
return leftRotate(n);
}
if(bf > 1) {
if(v > n.left.data) n.left = leftRotate(n.left);
return rightRotate(n);
}
return n;
}
Node rightRotate(Node r) {
Node x = r.left;
r.left = x.right;
x.right = r;
r.height = Integer.max(height(r.left), height(r.right))+1;
x.height = Integer.max(height(x.left), height(x.right))+1;
return x;
}
Node leftRotate(Node r) {
Node x = r.right;
r.right = x.left;
x.left = r;
r.height = Integer.max(height(r.left), height(r.right))+1;
x.height = Integer.max(height(x.left), height(x.right))+1;
return x;
}
int depth(Node n)
{
if(n == null) return 0;
return Integer.max(height(n.left), height(n.right))+1;
}
void lvlOrd(Node n) // LevelOrder Traversal - BFS
{
ArrayDeque <Node>q = new ArrayDeque<>();
q.add(n);
while( !q.isEmpty() ){
n = q.poll();
System.out.print(n.data + " ");
if(n.left != null) q.add(n.left);
if(n.right != null) q.add(n.right);
}
}
void inorder(Node n) // InOrder Traversal - DFS (Ascending)
{
if(n == null) return;
inorder(n.left);
System.out.print(n.data + " ");
inorder(n.right);
}
void preorder(Node n) // PreOrder Traversal - DFS
{
if(n == null) return;
System.out.print(n.data + " ");
preorder(n.left);
preorder(n.right);
}
void postorder(Node n) // PostOrder Traversal - DFS
{
if(n == null) return;
postorder(n.left);
postorder(n.right);
System.out.print(n.data + " ");
}
}
public class Solution
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
AVLTree bt = new AVLTree();
int n = sc.nextInt();
for(int i=0;i<n;i++){
bt.insert(sc.nextInt());
}
System.out.println("-------------------------AVL
Tree-------------------------");
System.out.println("DFS: ");
System.out.print("IN-ORDER: ");
bt.inorder(bt.root);
System.out.print("\nPRE-ORDER: ");
bt.preorder(bt.root);
System.out.print("\nPOST-ORDER: ");
bt.postorder(bt.root);
System.out.println("\nBFS: ");
System.out.print("Level-Order: ");
bt.lvlOrd(bt.root);
}
}
