Binary Search tree Array implementation C++

Question

I am in the process of implementing a Binary Search tree that gets represented using the Array implementation. This is my code so far: Take note that I have done with the Structure of tree and it is being saved as a Linked List. I want to convert this linked list into an array.

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.

Am I overthinking this problem? Can there be a Recursion?

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.

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

using namespace std;

struct node { 
    int data; 
    struct node* left; 
    struct node* right; 
};

void inorder(struct node* node){
    if(node){
        inorder(node->left);
        cout << node->data << " ";
        inorder(node->right);
    }
}

void insert(struct node** node, int key){

    if(*node == NULL){
        (*node) = (struct node*)malloc(sizeof(struct node));
        (*node)->data = key;
        (*node)->left = NULL;
        (*node)->right = NULL;
        printf("inserted node with data %d\n", (*node)->data);
    }
    else if ((*node)->data > key){
        insert((&(*node)->left),key);

    }
    else
        insert((&(*node)->right),key);
}

int max_tree(struct node* node){
    int left,right;
    if(node == NULL)
       return 0;
    else
    {
      left=max_tree(node->left);
      right=max_tree(node->right);
      if(left>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(&root, 10);
    insert(&root, 20);
    insert(&root, 5);
    insert(&root, 2);


   inorder(root);
   cout << endl;
   cout << "Height is: ";
   cout << max_tree(root);
   h = max_tree(root)
   return_array(root, h)
}

Answer 1

Considering that you want to efficiently store a binary search tree, using

l = 2i + 1
r = 2i + 2

will waste space every time your tree encounters a leaf node that is not occurring at the end of the tree (breadth-first). Consider the following simple example:

  2
 / \
1   4
   / \
  3   5

This (when transformed breadth-first into an array) results in

[ 2, 1, 4, -, -, 3, 5 ]

And wastes two slots in the array.

Now if you want to store the same tree in an array without wasting space, just transform it into an array depth-first:

[ 2 1 4 3 5 ]

To recover the original tree from this, follow these steps for each node:

1. Choose the first node as root

2. For each node (including root), choose

   a) the left child as the next smaller key from the array after the current key

   b) the right child as the next bigger key from the array, being no larger than the smallest parent key encountered when last branching left, and smaller than the direct parent's key when you are currently in it's left branch

Obviously finding the correct b) is slightly more complex, but not too much. Refer to my code example here.

If I'm not mistaken, transforming to and from an array will take O(n) in either case. And as no space is wasted, space complexity is also O(n).

This works because binary search trees have more structure than ordinary binary trees; here, I'm just using the binary search tree property of the left child being smaller, and the right child being larger than the current node's key.

EDIT:

After doing some further research on the topic, I found that reconstructing the tree in preorder traversal order is much simpler. The recursive function doing that is implemented here and here, respectively.

It basically consists of these steps:

• As long as the input array has unseen entries,
  • If the value to insert is greater than the current branch's minimum value and less than the current branch's maximum allowed,
    • Add a node to the tree at the current position and set it's value to the current input value
    • Remove current value from input
  • If there are items left in the input,
    • Recurse into the left child
    • Recurse into the right child

The current minimum and maximum values are defined by the position inside the tree (left child: less than parent, right child: greater than parent).

For more elaborate details, please refer to my source code links.

Answer 2

If you want to store the tree node in a array,you had better to start from 1 position of your array!So the relation between the parent and its children should be simple:

parent = n;
left = 2n;
right = 2n + 1;

you should BFS the tree,and store the node in the array(If the node is null you should also store in the array using a flag ex 0),you should get the very array of the tree!

Answer 3

To do this you have to follow these steps.

1. Create an empty queue.
2. Make the first node of the list as root, and enqueue it to the queue.

3. Until we reach the end of the list, do the following.

   a. Dequeue one node from the queue. This is the current parent.

   b. Traverse two nodes in the list, add them as children of the current parent.

   c. Enqueue the two nodes into the queue.

Time Complexity: Time complexity of the above solution is O(n) where n is the number of nodes.