title: Binary Search tree Array implementation C++
body: <p>I am in the process of implementing a Binary Search tree that gets represented using the Array implementation. This is my code so far: <strong>Take note that I have done with the Structure of tree and it is being saved as a Linked List.</strong> I want to convert this linked list into an array.</p>
  
  <p>My thoughts on how to go about this are as followed. Make a return_array function. Have the Size of the array set to the Max number of nodes( 2^(n-1)+1) and go through the linked list. Root node would be @ position 0 on the array then his L-child = (2*[index_of_parent]+1) and R-child = (2*[index_of_parent]+2). I looked around for a bit and searched to find something that can get me an idea of how I can keep track of each node and how I can go through each one.</p>
  
  <p>Am I overthinking this problem?
  Can there be a Recursion?</p>
  
  <p>Also, I'm considering creating a visual tree instead of an array but have no idea how to space it out correctly. If anyone has an idea on how to do that it would be awesome to get a better understanding of that.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;cmath&gt;
  
  using namespace std;
  
  struct node { 
      int data; 
      struct node* left; 
      struct node* right; 
  };
  
  void inorder(struct node* node){
      if(node){
          inorder(node-&gt;left);
          cout &lt;&lt; node-&gt;data &lt;&lt; " ";
          inorder(node-&gt;right);
      }
  }
  
  void insert(struct node** node, int key){
  
      if(*node == NULL){
          (*node) = (struct node*)malloc(sizeof(struct node));
          (*node)-&gt;data = key;
          (*node)-&gt;left = NULL;
          (*node)-&gt;right = NULL;
          printf("inserted node with data %d\n", (*node)-&gt;data);
      }
      else if ((*node)-&gt;data &gt; key){
          insert((&amp;(*node)-&gt;left),key);
  
      }
      else
          insert((&amp;(*node)-&gt;right),key);
  }
  
  int max_tree(struct node* node){
      int left,right;
      if(node == NULL)
         return 0;
      else
      {
        left=max_tree(node-&gt;left);
        right=max_tree(node-&gt;right);
        if(left&gt;right)
           return left+1;
        else
           return right+1;
  }
  }
  
  //This is where i dont know how to keep the parent/children the array.
  void return_array(struct node* node, int height){
      int max;
      height = height - 1;
      max = pow(2, height) - 1;
      int arr [height];
  
  
  
  
  
  
  
  
  }
  
  int main(){
      int h;
      struct node* root = NULL;
  
      insert(&amp;root, 10);
      insert(&amp;root, 20);
      insert(&amp;root, 5);
      insert(&amp;root, 2);
  
  
     inorder(root);
     cout &lt;&lt; endl;
     cout &lt;&lt; "Height is: ";
     cout &lt;&lt; max_tree(root);
     h = max_tree(root)
     return_array(root, h)
  }
  </code></pre>