W3Schools Tryit Editor

Python

Java

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1

def getHeight(node):
    if not node:
        return 0
    return node.height

def getBalance(node):
    if not node:
        return 0
    return getHeight(node.left) - getHeight(node.right)

def rightRotate(y):
    print('Rotate right on node',y.data)
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    y.height = 1 + max(getHeight(y.left), getHeight(y.right))
    x.height = 1 + max(getHeight(x.left), getHeight(x.right))
    return x

def leftRotate(x):
    print('Rotate left on node',x.data)
    y = x.right
    T2 = y.left
    y.left = x
    x.right = T2
    x.height = 1 + max(getHeight(x.left), getHeight(x.right))
    y.height = 1 + max(getHeight(y.left), getHeight(y.right))
    return y

def insert(node, data):
    if not node:
        return TreeNode(data)

if data < node.data:
        node.left = insert(node.left, data)
    elif data > node.data:
        node.right = insert(node.right, data)

node.height = 1 + max(getHeight(node.left), getHeight(node.right))
    balance = getBalance(node)

# Left Left
    if balance > 1 and data < node.left.data:
        return rightRotate(node)

# Right Right
    if balance < -1 and data > node.right.data:
        return leftRotate(node)

# Left Right
    if balance > 1 and data > node.left.data:
        node.left = leftRotate(node.left)
        return rightRotate(node)

# Right Left
    if balance < -1 and data < node.right.data:
        node.right = rightRotate(node.right)
        return leftRotate(node)

return node

def inOrderTraversal(node):
    if node is None:
        return
    inOrderTraversal(node.left)
    print(node.data, end=", ")
    inOrderTraversal(node.right)

# Inserting nodes
root = None
letters = ['C', 'B', 'E', 'A', 'D', 'H', 'G', 'F']
for letter in letters:
    root = insert(root, letter)

inOrderTraversal(root)

#Python

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    char data;
    struct TreeNode *left, *right;
    int height;
} TreeNode;

int max(int a, int b) {
    return (a > b) ? a : b;
}

int height(TreeNode *N) {
    if (N == NULL) return 0;
    return N->height;
}

TreeNode* newNode(char data) {
    TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return(node);
}

TreeNode *rightRotate(TreeNode *y) {
    printf("Rotate right on node %c\n", y->data);
    TreeNode *x = y->left;
    TreeNode *T2 = x->right;

x->right = y;
    y->left = T2;

y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

return x;
}

TreeNode *leftRotate(TreeNode *x) {
    printf("Rotate left on node %c\n", x->data);
    TreeNode *y = x->right;
    TreeNode *T2 = y->left;

y->left = x;
    x->right = T2;

x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

return y;
}

int getBalance(TreeNode *N) {
    if (N == NULL) return 0;
    return height(N->left) - height(N->right);
}

TreeNode* insert(TreeNode* node, char data) {
    if (node == NULL) return(newNode(data));

if (data < node->data) node->left = insert(node->left, data);
    else if (data > node->data) node->right = insert(node->right, data);
    else return node;

node->height = 1 + max(height(node->left), height(node->right));

int balance = getBalance(node);

if (balance > 1 && data < node->left->data) return rightRotate(node);
    if (balance < -1 && data > node->right->data) return leftRotate(node);
    if (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    if (balance < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

return node;
}

void inOrderTraversal(TreeNode *root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%c ", root->data);
        inOrderTraversal(root->right);
    }
}

int main() {
    TreeNode *root = NULL;
    char letters[] = {'C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'};
    int n = sizeof(letters) / sizeof(letters[0]);
    for (int i = 0; i < n; i++) {
        root = insert(root, letters[i]);
    }

inOrderTraversal(root);
    return 0;
}

//C

public class Main {
    static class AVLTree {
        class TreeNode {
            char data;
            TreeNode left, right;
            int height;

TreeNode(char d) {
                data = d;
                height = 1;
            }
        }

TreeNode root;

int height(TreeNode N) {
            if (N == null) return 0;
            return N.height;
        }

int getBalance(TreeNode N) {
            if (N == null) return 0;
            return height(N.left) - height(N.right);
        }

TreeNode rightRotate(TreeNode y) {
            System.out.println("Rotate right on node " + y.data);
            TreeNode x = y.left;
            TreeNode T2 = x.right;

x.right = y;
            y.left = T2;

y.height = Math.max(height(y.left), height(y.right)) + 1;
            x.height = Math.max(height(x.left), height(x.right)) + 1;

return x;
        }

TreeNode leftRotate(TreeNode x) {
            System.out.println("Rotate left on node " + x.data);
            TreeNode y = x.right;
            TreeNode T2 = y.left;

y.left = x;
            x.right = T2;

x.height = Math.max(height(x.left), height(x.right)) + 1;
            y.height = Math.max(height(y.left), height(y.right)) + 1;

return y;
        }

TreeNode insert(TreeNode node, char data) {
            if (node == null) return new TreeNode(data);

if (data < node.data) node.left = insert(node.left, data);
            else if (data > node.data) node.right = insert(node.right, data);
            else return node;

node.height = 1 + Math.max(height(node.left), height(node.right));

int balance = getBalance(node);

if (balance > 1 && data < node.left.data) return rightRotate(node);
            if (balance < -1 && data > node.right.data) return leftRotate(node);
            if (balance > 1 && data > node.left.data) {
                node.left = leftRotate(node.left);
                return rightRotate(node);
            }
            if (balance < -1 && data < node.right.data) {
                node.right = rightRotate(node.right);
                return leftRotate(node);
            }

return node;
        }

void inOrderTraversal(TreeNode node) {
            if (node != null) {
                inOrderTraversal(node.left);
                System.out.print(node.data + ", ");
                inOrderTraversal(node.right);
            }
        }
    }

public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        char[] letters = {'C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'};
        for (char letter : letters) {
            tree.root = tree.insert(tree.root, letter);
        }
        tree.inOrderTraversal(tree.root);
    }
}

//Java