Build an AVL Tree

Problem

Read an integer n, then n integer keys. Insert them in order into an initially empty AVL tree (duplicates are ignored). Then print the pre-order traversal (keys separated by single spaces) and the height of the tree. The height of an empty tree is −1 and of a single node 0. If the tree is empty, print (empty) instead of the keys.

Because the rotations change the shape, the pre-order traversal shows whether you rebalanced correctly.

Input:

5 10 20 30 40 50

Output:

Pre-order: 20 10 40 30 50
Height: 2

Empty input (0):

Pre-order: (empty)
Height: -1

Your solution

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.

import java.util.Scanner;

class AvlTree {
    private static class Node {
        int key;
        int height;          // leaf = 0
        Node left, right;
        Node(int key) { this.key = key; }
    }

private Node root;

private static int height(Node n) { return n == null ? -1 : n.height; }

// TODO: update(n), balance(n), rotateLeft, rotateRight, rebalance

public void insert(int key) {
        // TODO: recursive insert that rebalances on the way back up
    }

public int height() { return height(root); }

public String preOrder() {
        // TODO: return the keys separated by spaces, or "(empty)"
        return "";
    }
}

public class AvlBuild {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        AvlTree tree = new AvlTree();
        for (int i = 0; i < n; i++) {
            tree.insert(in.nextInt());
        }
        System.out.println("Pre-order: " + tree.preOrder());
        System.out.println("Height: " + tree.height());
    }
}

← D12.2 Deleting keys from a BST D13.2 AVL Rotation Log →