BinTree palyground, C++ (gcc)

BinTree palyground

//Title of this code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct BinTree {
  
    int data;
    BinTree *left;
    BinTree *right;
    
    BinTree(int d, BinTree* l, BinTree* r): data(d), left(l), right(r) {}
    
};

int depth(BinTree* root, int d) {
    if (!root) 
        return d;
    
    return max(depth(root->left, d + 1), depth(root->right, d + 1));
}

int maxDepth(int nodeCount) {
    int i = 0;
    while(nodeCount > 0) {
        nodeCount >>= 1;
        ++i;
    }
    return i;
}

void inorder(BinTree* root) {
    if (!root)
        return;
    
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

void resetTree(BinTree* root, vector<BinTree*>& t) {
    if (!root)
        return;
    
    resetTree(root->left, t);
    t.push_back(root);
    resetTree(root->right, t);
    
    root->left = NULL;
    root->right = NULL;
}

void BuildNew(vector<BinTree*>& t, BinTree*& root, int begin, int end) {
    if (begin > end)
        return;
    
    int mid;
    if (begin == end)
        mid = begin;
    else
        mid = (end - begin) / 2 + begin;
    
    root = t[mid];

BuildNew(t, root->left, begin, mid - 1);
    BuildNew(t, root->right, mid + 1, end);
}

void print(vector<BinTree*>& t) {
    for (unsigned i = 0; i < t.size(); ++i){
        cout << t[i]->data << " ";
          
    }
    cout << endl;
}

void printLevels(BinTree* root) {
 
    queue<BinTree*> *nodesCur = new queue<BinTree*>();
    queue<BinTree*> *nodesNext = new queue<BinTree*>();
    nodesCur->push(root);
    
    
    do {
        while (!nodesCur->empty()) {
    
            BinTree *cur = nodesCur->front();
            nodesCur->pop();
            
            cout << cur->data << " ";
            
            if (cur->left)
                nodesNext->push(cur->left);
            if (cur->right)
                nodesNext->push(cur->right);
        }
        cout << endl;
        swap(nodesCur, nodesNext);
        
    } while (!nodesCur->empty());
    
}

bool isBST(BinTree* root, int minVal, int maxVal) {
    if (!root)
        return true;
    
    if (root->data > minVal && root->data < maxVal)
        return isBST(root->left, minVal, root->data) && isBST(root->right, root->data, maxVal);

return false;
    
}

int treeHeight(BinTree* root) {
    if (!root)
        return 0;
    
    return max(treeHeight(root->left), treeHeight(root->right)) + 1;    
}

int treeDiameter(BinTree* root) {
    if (!root)
        return 0;
    
    int lheight = treeHeight(root->left);
    int rheight = treeHeight(root->right);
 
    int ldiameter = treeDiameter(root->left);
    int rdiameter = treeDiameter(root->right);

return max(lheight + rheight + 1, max(ldiameter, rdiameter));   
}

bool nodeCompare(BinTree* n1, BinTree* n2) {
    return n1->data < n2->data; 
}

int main()
{
    BinTree *ggg = new BinTree(6, NULL, NULL);
    BinTree *gg = new BinTree(18, NULL, ggg);
    BinTree *ddd = new BinTree(1, NULL, NULL);
    BinTree *dd = new BinTree(2, ddd, NULL);
    BinTree *hh = new BinTree(13, NULL, NULL);
    
    
    BinTree *j = new BinTree(10, NULL, NULL);
    BinTree *h = new BinTree(14, hh, NULL);
    BinTree *g = new BinTree(17, NULL, gg);
    BinTree *f = new BinTree(12, j, h);
    BinTree *e = new BinTree(7, NULL, NULL);
    BinTree *d = new BinTree(3, dd, NULL);
    BinTree *c = new BinTree(15, f, g);
    BinTree *b = new BinTree(5, d, e);
    BinTree *root = new BinTree(9, b, c);

cout << treeDiameter(root) << endl;
    //cout << treeHeight(root) << endl;

printLevels(root);
    
    cout << boolalpha << isBST(root, 0, 100) << endl;
    
    
    vector<BinTree*> t;
    
    inorder(root);
    cout << endl;
    
    
    cout << depth(root, 0);
    cout << endl;

resetTree(root, t);
    sort(t.begin(), t.end(), nodeCompare);
    root = t[t.size() / 2];
    BuildNew(t, root, 0, t.size() - 1);
    
    inorder(root);
    cout << endl;
    
    cout << depth(root, 0);
    cout << endl;
    
    
    cout << boolalpha << isBST(root, 0, 100) << endl;
    printLevels(root);
}


run \| edit \| history \| help	0