Store all the node pointers in an array of pointers for Binary Search Tree

Question!

Recently I was trying to manipulate the binary search tree and got stuck here. I want to have an array(array of pointers) inside which I want to store the pointers of each node of the binary search tree in in-order fashion. I DON'T NEED THE VALUE OF EACH NODE I need the pointers so that I can access their value, left subtree and right subtree. What I have done is

struct node{
int key;
struct node *left, *right;
};

node **arr;
int x=0;

void inorder(struct node *root){
if (root != NULL){
    inorder(root->left);

    //cout<<"X : "<<x<<endl;
    arr[x] = root;
    x++;
    printf("%d \n", root->key);
    inorder(root->right);
}
}

Please help. Thanks.



Answers

You can do that, but if sorted array of node pointers satisfies your needs, then you don't need a binary search tree: you can perform binary search on the array. This data structure has the same access speed as a tree (can be even slightly faster because data is tightly packed in memory) and is very memory efficient. But insertion of new data is costly: o(n). So this solution is not appropriate if many insertions are expected. But in this case by maintaining that sorted array you loose all benefits of tree structure.



This is probably the comma operator, which evaluates everything then discards everything except the right hand side value.

But, if operator,( char const*, string2 ) is overloaded it could do anything (where string2 is the type of string2).

Look for such overloads.

Note that if string2 is a std::string such overloads may make your program ill formed, no diagostic required. Won't stop people from doing it. And it may "work" and still permit , to (for example) cause concatination of strings.

By : Yakk


It's an obfuscation. The comma operator evaluates all the arguments from left to right but discards all arguments apart from the final one. The formal type of the entire expression is the type of the final argument.

(Note also that the comma itself is a sequencing point.)

string2 becomes the value in the map, under key string1.

By : Bathsheba


This video can help you solving your question :)
By: admin