   Array based Binary Search Trees
  I'm trying to wrap my head around this problem conceptually, psuedo code would help the best. Right now, I'm given the task to construct a Binary Search Tree without the use of nodes or a linked list (:[[[) and i'm told just to use a dynamically allocated array. While I get the basic principal of it, the only way I can solve the problem is on a case by case basis. As in, give me the list, I will put the root in index 0, the children in 1 and 2 and so on. How can this be done without the use of the linked list? Apart from me thinking that it's just a horrible idea anyway and i'm reinventing a square wheel (who does array based BSTs?!) I just am totally lost on how to approach-Insertion-Removal-Searching My code so far:*Note: excuse the random LOLZ comments...I get bored!//.h//BinaryTree.cpp - Interface of the BinaryTree class//Kesh Iyer//CS 240//Professor Williams#include <iostream>#include <string>using namespace std;#define DEFAULT 15#ifndef BINARYTREE_H#define BINARYTREE_Htypedef int Element;typedef Element *Elements;class binaryTree {public://Default constructorbinaryTree();//Copy constructorbinaryTree(const binaryTree & oldTree);//Destructor~binaryTree();//Overloaded Assignment Operatorconst binaryTree & operator=(const binaryTree & oldTree);//Mutators//*******************************************************************//*****Insert - Inserts a string (str) at a given index (index) *****//*******************************************************************void insert(Element key);//*******************************************************************//*****Remove - Removes a string at a given index (index) ***********//*******************************************************************void remove(Element key);//Accessors//*******************************************************************//*****Find - Returns a key at a given index (index) ****************//*******************************************************************int find (Element key);//*******************************************************************//*****printKey- Prints the result of the tree **********************//*******************************************************************void printKey();//*******************************************************************//*****printStr - Prints the strings in the tree in order ***********//*******************************************************************void printStr();void display(ostream & out) const;private:Elements binaryElements;int capacity;int size;};ostream & operator<< (ostream & out, const binaryTree binarytree);#endif//.cpp//BinaryTree.cpp - Implementation of the BinaryTree class#include <iostream>#include <new>using namespace std;#include "binaryTree.h"//***Requirements for a Dynamic Array://Default constructorbinaryTree::binaryTree() {binaryElements = new Element[DEFAULT];capacity = DEFAULT;size = 0;}//Copy constructorbinaryTree::binaryTree(const binaryTree & oldTree): capacity(oldTree.capacity), size(oldTree.size){//New array://int binaryElements[DEFAULT];if(binaryElements != 0){for (int i = 0; i < size; i++)binaryElements = oldTree.binaryElements;}else {cout<<"No memory to allocate storage for new tree!";exit(1);}}//DestructorbinaryTree::~binaryTree(){delete [] binaryElements;}//Overloaded Assignment Operatorconst binaryTree & binaryTree::operator=(const binaryTree & oldTree){if (this != &oldTree)    {    if (capacity != oldTree.capacity){    delete[] binaryElements;capacity = oldTree.capacity;//string binaryElements[capacity];if (binaryElements == 0) {cerr<< "Insufficient Memory";exit(1);}    }    size = oldTree.size;for (int i = 0; i < capacity; i++)binaryElements = oldTree.binaryElements;}return *this;}//Insertvoid binaryTree::insert(Element key){if (size == 0) { //Level 1binaryElements[0] = key;size++;return;}if (size == capacity) {binaryElements = new Element[capacity];}else {for (int i = 0; i < capacity; i++) {if (key < binaryElements && binaryElements[i*2+1] == 0) {binaryElements[i*2+1] = key;cout<<"Added left node into: "<<i<<"th spot"<<endl;size++;return;}if (key > binaryElements && binaryElements[i*2+2] == 0) {binaryElements[i*2+2] = key;cout<<"Added right node into: "<<i<<"th spot"<<endl;size++;return;}}}}//Deletevoid binaryTree::delete(Element key) {//Findint binaryTree::find(Element key) {bool found = false;int first = 0, loc;int last = capacity-1;while (first <= last && !found) {loc = (first+last)/2;if (key < binaryElements[loc])last = loc-1;else if (key > binaryElements[loc])first = loc+1;else {found = true;cout<<"ITEM WAS FOUND LOLZ :"<<binaryElements[loc];}}if (found == false) {cout<<"Item not found..."<<endl;exit(1);}return binaryElements[loc];}void binaryTree::display(ostream & out) const{   for (int i =0; i < capacity; i++) {   out<<binaryElements;}}Any takers?   
  What you probably want is a heap.   ;  Well, I'll address your insertion. First off the size of the array is determined by the number of levels, not the number of used entries. One of the big reasons why if you do this you need to height balance the tree. Otherwise n elements can take an array of up to 2^n-1 entries to store. Don't go through each node, go through each level. You check if the left or right node is zero, if it isn't that's your new current node. If you exhaust the current number of levels then you need to allocate a new level. Assuming the root is at level 0 adding level n requires growing the array by 2^n elements. The search gave you the index but it isn't a valid index until you grow the array.Use an internal search, i.e. protected. That search returns the index a node is at or would be inserted at. The public search uses it and checks whether the index is within the bounds of the array and an index for a used node. The insert uses it to determine whether it's a duplicate, can be placed in the current array or the array needs to be grown.Failing to find an entry should not terminate your program. Within the class when you reallocate the array you have to copy all the elements from the old array to the new array. You can't use the copy constructor because a class cannot reallocate itself, but rather just it's members.   ;  We can see that this is an assignment.You've been given a few hints (heaps), and you should probably think about it for yourself.Please read the FAQ;  We don't allow homework-help questions here.   