Answer to Question #247822 in C++ for Arijit

Question

Note:
You are instructed not to write the code. Otherwise you will be awarded 0 marks.

Given the following AVL tree, delete node 3 and rebalance the tree if required. State clearly which rotations you applied to which Nodes. Draw resultant tree after every step.
root=5
root->left =3
root->left->left=2
root->left->left->left=1
root->left->right =4
root->right =8
root->right->left=7
root->right->left->left =6
root->right - >right=10
root->right->right->left=9
root->right->right->right =11
root->right->right->right->right =12

Answer 1

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int data;
    struct Node *left, *right;

    Node(int data) {
        this->data=data;
    }
};

void store(Node *root, vector<Node *> &nodes) {
    if (root == nullptr) { return; }
    store(root->left, nodes);
    nodes.push_back(root);
    store(root->right, nodes);
}

Node *buildUtil(vector<Node *> &nodes, int start, int end) {
    if (start > end) { return nullptr; }
    int mid = (start + end) / 2;
    Node *root = nodes[mid];
    root->left = buildUtil(nodes, start, mid - 1);
    root->right = buildUtil(nodes, mid + 1, end);
    return root;
}

Node *build(Node *root) {
    vector<Node *> nodes;
    store(root, nodes);
    return buildUtil(nodes, 0, nodes.size() - 1);
}

int main() {
    struct Node *root = new Node(5);
    root->left = new Node(3);
    root->left->left = new Node(2);
    root->left->left->left = new Node(1);
    root->left->right = new Node(4);
    root->right = new Node(8);
    root->right->left = new Node(7);
    root->right->left->left = new Node(6);
    root->right->right = new Node(10);
    root->right->right->left = new Node(9);
    root->right->right->right = new Node(11);
    root->right->right->right->right = new Node(12);
    
    struct Node *tmp = root->left;
    
    root->left = tmp->left;
    root->left->right = tmp->right;
    root = build(root);
    
    delete tmp;
    
    return 0;
}