HeapTree.cpp

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

struct Node
{
    string data;
    Node* LChild = NULL;
    Node* RChild = NULL;

    Node(string str){
        data = str;
    }
} *root = NULL;

void insert(vector<Node*>&v,int index){
    int parentIndex = (index - 1)/2;
    if (v[parentIndex]->LChild == NULL)
    {
        v[parentIndex]->LChild = v[v.size()-1];
    }
    else if (v[parentIndex]->RChild == NULL)
    {
        v[parentIndex]->RChild = v[v.size()-1];
    }
    
}
void mirror(Node* node){
    if (node == NULL || node->LChild == NULL || node->RChild == NULL)
    {
        return;
    }
    Node* temp = node->RChild;
    node->RChild = node->LChild;
    node->LChild = temp;

    mirror(node->LChild);
    mirror(node->RChild);
}
void preOrder(Node* node){
    if (node != NULL)
    {
        cout<<node->data<<" ";
        preOrder(node->LChild);
        preOrder(node->RChild);
    }
    
}
// void Predecessors(vector<Node*> v,int index){
//     int parentIndex = (index - 1)/2;
//     while (parentIndex >= 0 && v[parentIndex] != NULL)
//     {
//         cout<< v[parentIndex]->data;
//         index = parentIndex;
//         parentIndex = (index - 1)/2;
//     }
    
// }

//Predecssor: the node with the largest value less than x
//successor: the node with the smallest value greater than x
void findPreSuc(Node* node, Node*& pre, Node*& suc, string key) {
    if (node == NULL) return;

    if (node->data == key) {
        // Find predecessor: RChildmost in left subtree
        if (node->LChild != NULL) {
            Node* temp = node->LChild;
            while (temp->RChild)
                temp = temp->RChild;
            pre = temp;
        }
        // Find successor: LChildmost in right subtree
        if (node->RChild != NULL) {
            Node* temp = node->RChild;
            while (temp->LChild)
                temp = temp->LChild;
            suc = temp;
        }
    }
    else if (node->data > key) {
        // Current node might be successor
        suc = node;
        findPreSuc(node->LChild, pre, suc, key);
    }
    else {
        // Current node might be predecessor
        pre = node;
        findPreSuc(node->RChild, pre, suc, key);
    }
}
int height(Node* node,int h,string data){
    int lh,rh;
    if (node == NULL || node->data == data)
    {
        return h;
    }
    h++;
    lh = height(node->LChild,h,data);
    rh = height(node->RChild,h,data);
    if (lh > rh)
    {
        h = lh;
    }
    else{
        h = rh;
    }
    return h;
}
int BFS(Node* node){
    queue<Node*> q;
    int depth = 0;
    q.push(node);
    while (!q.empty())
    {
        int levelsize = q.size();
        for (size_t i = 0; i < levelsize; i++)
        {
            Node* temp = q.front();
            q.pop();
            if (temp->LChild != NULL)
            {
                q.push(temp->LChild);
            }
            if (temp->RChild != NULL)
            {
                q.push(temp->RChild);
            }
        }
        depth++;
    }
    return depth - 1;
}
int BSTsize(Node* node){
    int Lcount = 0;
    int Rcount = 0;
    if (node == NULL)
    {
        return 0;
    }
    Lcount = BSTsize(node->LChild);
    Rcount = BSTsize(node->RChild);
    return Lcount + Rcount + 1; 
}
int main(int argc, char const *argv[])
{
    vector<Node*>v;
    string data;
    for (size_t i = 0; i < 6; i++)
    {
        cout<<"enter data: ";
        cin>> data;
        v.push_back(new Node(data));
        if (i == 0)
        {
            root = v[0];
        }
        else{
            insert(v,i);
        }
    }
    preOrder(root);
    cout<<endl;
    //cout<<height(root,-1,"B"); //height of a tree
    mirror(root);
    preOrder(root);
    Node* pre = NULL;
    Node* suc = NULL;
    findPreSuc(root,pre,suc,v[0]->data);
    if (pre != NULL) cout << "Predecessor: " << pre->data << endl;
    else cout << "No Predecessor" << endl;
    if (suc != NULL) cout << "Successor: " << suc->data << endl;
    else cout << "No Successor" << endl;
    
    //BFS to find the height of the tree
    int h = BFS(root);
    cout<<"Height using BFS: "<<h;
    cout<<BSTsize(root);
    return 0;
}