Media.net Overall Interview Questions + Coding Solutions codewindow.in

#include <iostream>
#include <algorithm>
 
using namespace std;
 
class Node
{
    public:
        int key;
        Node *left;
        Node *right;
        int height;
};
 
// Function to calculate the height of a node
int height(Node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}
 
// Function to get the maximum of two integers
int max(int a, int b)
{
    return (a > b)? a : b;
}
 
// Function to right rotate subtree rooted with y
Node *rightRotate(Node *y)
{
    Node *x = y->left;
    Node *T2 = x->right;
 
    // Perform rotation
    x->right = y;
    y->left = T2;
 
    // Update heights
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    // Return new root
    return x;
}
 
// Function to left rotate subtree rooted with x
Node *leftRotate(Node *x)
{
    Node *y = x->right;
    Node *T2 = y->left;
 
    // Perform rotation
    y->left = x;
    x->right = T2;
 
    // Update heights
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;
 
    // Return new root
    return y;
}
 
// Function to get the balance factor of a node
int getBalance(Node *N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
 
// Function to insert a new key into the tree
Node* insert(Node* node, int key)
{
    /* 1. Perform the normal BST insertion */
    if (node == NULL)
        return (new Node(key));
 
    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);
 
    /* 2. Update height of this ancestor node */
    node->height = max(height(node->left), height(node->right)) + 1;
 
    /* 3. Get the balance factor of this ancestor node to check whether
       this node became unbalanced */
    int balance = get