Rotate the root – Data Structures Practice Problem

Practise the one move behind every balanced tree: rotating a node with its child.

What to build

The two rotation functions, applied at the root of a binary search tree.

Requirements

Build a plain binary search tree from the keys. The starter does this.
R rotates the root to the right, so its left child becomes the new root. L rotates the root to the left, so its right child becomes the new root.
Skip a rotation when the child that would become the root does not exist.
After all the rotations, print the keys in preorder.

Input

The first line has n, and the second has n different keys. The third line has q, and the fourth has q letters, each L or R, separated by spaces.

Output

The keys in preorder on one line, separated by spaces.

Constraints

1 ≤ n ≤ 100 and 1 ≤ q ≤ 100.

Example

Input:

Output:

2 1 3

Why it works

A rotation moves one subtree across and swaps a parent with its child. Every key stays on the correct side of every other key, so the tree is still a search tree, and only its shape and height change.

Examples

Example 1 · Input

Expected output

2 1 3

Example 2 · Input

Expected output

2 1 3

Hints

Hint 1

For a right rotation at y: x is y's left child. y takes x's right subtree as its left, and then y becomes x's right child.

Hint 2

A left rotation is the mirror image.

Hint 3

Each function returns the new top of the subtree, and the caller must store it.

Solution

Show one correct solution (try it yourself first)

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

typedef struct tree {
    int key;
    struct tree *left, *right;
} Tree;

Tree *insert(Tree *t, int key) {
    if (t == NULL) {
        Tree *n = malloc(sizeof(Tree));
        n->key = key;
        n->left = NULL;
        n->right = NULL;
        return n;
    }
    if (key < t->key) t->left = insert(t->left, key);
    else if (key > t->key) t->right = insert(t->right, key);
    return t;
}

Tree *rotate_right(Tree *y) {
    Tree *x = y->left;
    if (x == NULL) return y;
    y->left = x->right;
    x->right = y;
    return x;
}

Tree *rotate_left(Tree *x) {
    Tree *y = x->right;
    if (y == NULL) return x;
    x->right = y->left;
    y->left = x;
    return y;
}

void preorder(Tree *t, int *first) {
    if (t == NULL) return;
    if (!*first) printf(" ");
    *first = 0;
    printf("%d", t->key);
    preorder(t->left, first);
    preorder(t->right, first);
}

void free_tree(Tree *t) {
    if (t == NULL) return;
    free_tree(t->left);
    free_tree(t->right);
    free(t);
}

int main(void) {
    int n, q;
    scanf("%d", &n);
    Tree *root = NULL;
    for (int i = 0; i < n; i++) {
        int key;
        scanf("%d", &key);
        root = insert(root, key);
    }
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        char op[2];
        scanf("%1s", op);
        if (op[0] == 'L') root = rotate_left(root);
        else root = rotate_right(root);
    }
    int first = 1;
    preorder(root, &first);
    printf("\n");
    free_tree(root);
    return 0;
}

Lesson: AVL trees: self-balancing search trees →