why did we used *preorderIdx instead of preorderIdx?

Question

So, in this problem, we are supposed to construct a BST from a given preorder sequence. preorder[] is the array of size n, and preorderIdx denotes the index which starts at 0.

In the constructBST() function, why did we pass the argument of preorderIdx as a pointer? Inside the function, why did we use *preorderIdx instead of preorderIdx? While calling the constructBST() function in root->left and root->right, why did we not use *preorderIdx? Can anyone explain this to me?

#include<bits/stdc++.h>
using namespace std;

struct Node{
    int data;
    struct Node* left;
    struct Node* right;
    Node(int val){
        data = val;
        left = NULL;
        right = NULL;
    }
};


Node * constructBST(int preorder[], int*preorderIdx, int key, int min, int max, int n){
    if(*preorderIdx>=n){
        return NULL;
    }
    
    Node* root = NULL;
    if(key> min && key<max){
        root = new Node(key);
        *preorderIdx = *preorderIdx +1;
        if(*preorderIdx<n){
            root->left = constructBST(preorder,preorderIdx,preorder[*preorderIdx],min,key,n);
        }
        if(*preorderIdx<n){
            root->right = constructBST(preorder,preorderIdx,preorder[*preorderIdx],key,max,n);
        }
    }
    
    return root;
}


void inorder(Node* root){
    if(root==NULL){
        return;
    }
    inorder(root->left);
    cout<< root->data<<" ";
    inorder(root->right);
}

void printPreorder(Node* root){
    if(root==NULL){
        return;
    }
    cout<< root->data<<" ";
    printPreorder(root->left);
    
    printPreorder(root->right);
}


int main(){
    
    int preorder[]={10,2,1,13,11};
    int n =5;
    int preorderIdx =0;
    Node * root = constructBST(preorder,preorderIdx,preorder[0],INT_MIN,INT_MAX,n);
    printPreorder(root);
    
}

The code shown will not compile, as `main()` is trying to call `constructBST()` passing it an `int` where an `int*` is expected. `constructBST(...,preorderIdx,...)` needs to be `constructBST(...,&preorderIdx,...)` instead — Remy Lebeau, Jun 22 '21 at 20:47
Passing pointers to variables is commonly used in C to emulate pass by reference. You might want to invest in [some good C++ books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) to learn C++ properly instead of using so-called "competition" sites. Code used on such sites typically range from bad to truly awful (the kind of awful that can make the author of the code virtually unemployable). — Some programmer dude, Jun 22 '21 at 20:47
What reference are you using, that tells to use ``. It's not standard. You should get a different reference. — Thomas Matthews, Jun 22 '21 at 21:01

jtbandes · Answer 1 · 2021-06-22T21:09:07.047

2

These are great questions!

why did we passed the argument of preorderIdx as a pointer?

Because constructBST modifies preorderIdx (*preorderIdx = *preorderIdx +1;) and it wants these changes to be visible to the caller.

inside the function we used *preorderIdx instead of preorderIdx why?

Simply because it's a pointer. The function is declared with int *preorderIdx, so to access the int, we write *preorderIdx.

While calling the constructBST() function in root->left and root->right, why did we not use *preorderIdx?

Because we're passing the same pointer to the recursive call. We're not passing a pointer to a different integer.

edited Jun 22 '21 at 21:09

answered Jun 22 '21 at 20:47

jtbandes

115,675
35
233
266

Ok, got it till now. But, then why did we use preorder[*preorderIdx] in roo->left and roo->right ? – Anonymous User Jun 22 '21 at 21:08
in both of the lines why can't we use preorder[preorderIdx] instead of preorder[*preorderIdx] ? – Anonymous User Jun 22 '21 at 21:13
@AnonymousUser Because `preorderIdx` is a *pointer* to the index, and not the index itself? You definitely need to read some good books or take some classes. where all this should be covered. – Some programmer dude Jun 22 '21 at 21:26
@Someprogrammerdude I am really stuck in pointers. That's the reason why python was easy then c++. But i really need to learn pointers. So, can you tell me some good resources for pointers?? Maybe some youtube videos. Coz its kinda difficult to understand on my own. – Anonymous User Jun 22 '21 at 21:31

why did we used *preorderIdx instead of preorderIdx?

1 Answers1