• : this is always true for a binary tree.

• Parent of any node at index i will be at index
  

We can fill the elements in the array level-by-level, make sure to take into account empty nodes

• ! Note that the array indexing here starts from 1, we can simply ignore the index 0 and start from 1.

• Here notice that the total null pointers will be equal to total nodes + 1. This is similar to the case of strict binary tree where the total number of leaf nodes were equal to total number of internal nodes + 1

• Stack will be used.
  

DIY : Easy hai

This is a little complex.

• When you are pushing the address of a node for the second time in the stack, we'll have to convert that address to an integer and then store negative of that integer in the stack so as to know if we have to print that node or not. If the address is negative then print the node otherwise continue forward.
  

Time Complexity is where height is the height of the BST.

• We assume the height of a BST with n number of nodes to be minimum.

Recursive Approach :

Iterative Approach :

• For the element that is to be deleted, we'll find the Inorder predecessor and Inorder Successor of that node. Then the deleted Node can be replaced with either of these nodes.
• Inorder Predecessor of a Node : Right Most child of the left child.
• Inorder Successor of a Node : Leftmost child of the right most child.
  
  But what if we are deleting a node with only 1 child or with no child at all.
  Or what if the inorder predecessor or inorder successor have child node/s ? Then we'll have to the replace the inorder successor/predecessor with it's inorder successor or predecessor.
• 
• Examples :
  

#include <iostream>

using namespace std;
 
class Node{
public:
    Node* lchild;
    int data;
    Node* rchild;
};
 
class BST{
private:
    Node* root;
public:
    BST(){ root = nullptr; }
    Node* getRoot(){ return root; }
    void iInsert(int key);
    void Inorder(Node* p);
    Node* iSearch(int key);
    Node* rInsert(Node* p, int key);
    Node* rSearch(Node* p, int key);
    Node* Delete(Node* p, int key);
    int Height(Node* p);
    Node* InPre(Node* p);
    Node* InSucc(Node* p);
};
 
void BST::iInsert(int key) {
 
    Node* t = root;
    Node* p;
    Node* r;
 
    // root is empty
    if (root == nullptr){
        p = new Node;
        p->data = key;
        p->lchild = nullptr;
        p->rchild = nullptr;
        root = p;
        return;
    }
 
    while(t != nullptr){
        r = t;
        if (key < t->data){
            t = t->lchild;
        } else if (key > t->data){
            t = t->rchild;
        } else {
            return;
        }
    }
 
    // Now t points at NULL and r points at insert location
    p = new Node;
    p->data = key;
    p->lchild = nullptr;
    p->rchild = nullptr;
 
    if (key < r->data){
        r->lchild = p;
    } else {
        r->rchild = p;
    }
 
}
 
void BST::Inorder(Node* p) {
    if (p){
        Inorder(p->lchild);
        cout << p->data << ", " << flush;
        Inorder(p->rchild);
    }
}
 
Node* BST::iSearch(int key) {
    Node* t = root;
    while (t != nullptr){
        if (key == t->data){
            return t;
        } else if (key < t->data){
            t = t->lchild;
        } else {
            t = t->rchild;
        }
    }
    return nullptr;
}
 
Node* BST::rInsert(Node *p, int key) {
    Node* t;
    if (p == nullptr){
        t = new Node;
        t->data = key;
        t->lchild = nullptr;
        t->rchild = nullptr;
        return t;
    }
 
    if (key < p->data){
        p->lchild = rInsert(p->lchild, key);
    } else if (key > p->data){
        p->rchild = rInsert(p->rchild, key);
    }
    return p;  // key == p->data?
}
 
Node* BST::rSearch(Node *p, int key) {
    if (p == nullptr){
        return nullptr;
    }
 
    if (key == p->data){
        return p;
    } else if (key < p->data){
        return rSearch(p->lchild, key);
    } else {
        return rSearch(p->rchild, key);
    }
}
 
Node* BST::Delete(Node *p, int key) {
    Node* q;
 
    if (p == nullptr){
        return nullptr;
    }
 
    if (p->lchild == nullptr && p->rchild == nullptr){
        if (p == root){
            root = nullptr;
        }
        delete p;
        return nullptr;
    }
 
    if (key < p->data){
        p->lchild = Delete(p->lchild, key);
    } else if (key > p->data){
        p->rchild = Delete(p->rchild, key);
    } else {
        if (Height(p->lchild) > Height(p->rchild)){
            q = InPre(p->lchild);
            p->data = q->data;
            p->lchild = Delete(p->lchild, q->data);
        } else {
            q = InSucc(p->rchild);
            p->data = q->data;
            p->rchild = Delete(p->rchild, q->data);
        }
    }
    return p;
}
 
int BST::Height(Node *p) {
    int x;
    int y;
    if (p == nullptr){
        return 0;
    }
    x = Height(p->lchild);
    y = Height(p->rchild);
    return x > y ? x + 1 : y + 1;
}
 
Node* BST::InPre(Node *p) {
    while (p && p->rchild != nullptr){
        p = p->rchild;
    }
    return p;
}
 
Node* BST::InSucc(Node *p) {
    while (p && p->lchild != nullptr){
        p = p->lchild;
    }
    return p;
}
 
 
int main() {
 
    BST bst;
 
    // Iterative insert
    bst.iInsert(10);
    bst.iInsert(5);
    bst.iInsert(20);
    bst.iInsert(8);
    bst.iInsert(30);
 
    // Inorder traversal
    bst.Inorder(bst.getRoot());
    cout << endl;
 
    // Iterative search
    Node* temp = bst.iSearch(2);
    if (temp != nullptr){
        cout << temp->data << endl;
    } else {
        cout << "Element not found" << endl;
    }
 
    // Recursive search
    temp = bst.rSearch(bst.getRoot(), 20);
    if (temp != nullptr){
        cout << temp->data << endl;
    } else {
        cout << "Element not found" << endl;
    }
 
    // Recursive insert
    bst.rInsert(bst.getRoot(), 50);
    bst.rInsert(bst.getRoot(), 70);
    bst.rInsert(bst.getRoot(), 1);
    bst.Inorder(bst.getRoot());
    cout << "\n" << endl;
 
    // Inorder predecessor and inorder successor
    BST bs;
    bs.iInsert(5);
    bs.iInsert(2);
    bs.iInsert(8);
    bs.iInsert(7);
    bs.iInsert(9);
    bs.iInsert(1);
 
    temp = bs.InPre(bs.getRoot());
    cout << "InPre: " << temp->data << endl;
 
    temp = bs.InSucc(bs.getRoot());
    cout << "InSucc: " << temp->data << endl;
 
    bs.Inorder(bs.getRoot());
    cout << endl;
 
    // Delete
    bs.Delete(bs.getRoot(), 7);
    bs.Inorder(bs.getRoot());
    
    return 0;
}
Copy

To balance a node of an AVL tree we perform rotations.

Deletion from AVL tree is similar to Deletion from Binary Search Tree :

• First search for the key that you want to delete, if found delete it. Then either Inorder Successor or Inorder Predecessor will take it's place.
• Then if any node is imbalanced we'll perform rotations.
• 

• Here 40 is inserted into the heap, but after insertion it no longer remains a Max Heap. Therefore we'll have to fix it.
  • To fix it, we compare the value of 40 with it's parent, for max heap if then we'll swap them both. To swap, we'll keep 40 in some temporary variable and replace the value at 40's place with 5 and leave 5's place as empty, now, since 40>20 also, therefore 20 will be placed at the original place of 5. This process continues as long as the condition is satisfied.
  • 
    • At last we'll copy 40 at the empty place.
• In the array it is done like this :
  
  This is the original array, the array in the image below is the final array after the insertion process has been completed.

• 
• 
  • Time Complexity of insertion of 1 element is : height of the tree i.e
  • We'll always add the node to the leaf, then we'll call the insert function which will then rearrange the elements of the array.

In heap we can only delete the largest element (we are talking about the max heap here) i.e. the root element. In other words only the highest priority element can be deleted from the heap.

• After the deletion of the root element the last element in the BT will be moved to the root node.
  
  
  Now this is no longer a max heap, we'll have to fix this.

We'll do the same thing in the array :

• 
  • take out the value 40 and store it in variable x then move 5 at at the place of 40
• 
• 
  Compare the children of new root, whichever one is greater will then be compared with the root and then will get swapped with the root if that element is greater than the root (for max heap ofc).
• 
  Now do this process again by taking the children of 5 and swap if necessary.
• 

In array :

• If i is the root, compare 2i and 2i+1 then compare the greater element with the parent and swap if child > root.

• Basically jo element delete kiya hai wo maximum element hoga. And since array me ab ek space khali hai end me therefore delete element ko ham last me place kar denge and size ko n-1 kar dege taaki element delete bhi ho jaye from the heap and ham store bhi kar sake deleted element ko.
• We perform the delete function 1 by 1 and store the elements from last to first then we'll get a sorted array. this is called heap sort.
• For more see Abdul Bari sir's Lecture.

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

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

void insert(int a[], int n)
{
    int x = a[n];
    int i = n;
    while (i > 1 && a[i / 2] < x)
    {
        a[i] = a[i / 2];
        i = i / 2;
    }
    a[i] = x;
}

int delete(int a[], int n)
{
    int i = 1, j = 2 * i;
    int x = a[i];
    a[i] = a[n];
    a[n] = x;

    while (j < n - 1)
    {
        if (a[j + 1] > a[j])
            j = j + 1;
        if (a[j] > a[i])
        {
            swap(&a[i], &a[j]);

            i = j;
            j = 2 * i;
        }
        else
            break;
    }
    return x;
}

int main()
{

    int a[] = {0, 10, 20, 30, 25, 5, 40, 35};

    for(int i =1; i<=7; i++)
        insert(a, i);


    for(int i = 7; i>=1; i--)
        delete(a, i);

    // Heap Sort
    for(int i = 1; i<=7; i++)
        printf("%d ", a[i]);

    return 0;
}
Copy

• In create heap we adjust from bottom to up and start from the first element of the array of binary tree where as in heapify we adjust towards the bottom and start from the last element in the array
• 
• Where as create heap has O(n * log n) time complexity.