0

Here is my insert method:

void BST::insert(Node* cur, int x) { //private method
    if (!cur) {
        cur = new Node(x);
    }

    else {
        if (x < cur->val) {
            if (cur->left) {
                insert(cur->left, x);
            }

            else {
                cur->left = new Node(x);
            }
        }

        else if (x > cur->val) {
            if (cur->right) {
                insert(cur->right, x);
            }

            else {
                cur->right = new Node(x);
            }
        }
    }
}

void BST::insert(int x) { //public method
    insert(root, x); //root is the root of the tree (private variable)
}

It works if my root pointer is not NULL. However, if the root is NULL, it doesn't construct into a Node pointer. Since pointers pass by reference, shouldn't it save outside of the function scope? Thanks

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
N. Gupta
  • 1
  • 1
  • `Since pointers pass by reference` *references* pass by reference, `cur` is not a reference, if you want to make it a reference then say so: `Node*& cur`. – user657267 Oct 05 '15 at 05:00
  • Use a separate method to to initialize the tree if its root is null. See a BST example to be clear. – Abhishek Ranjan Oct 05 '15 at 06:05
  • Use the code below for insert(x) void BST::insert(int x) { //public method if(root==NULL){ root=new Node(x); return; } insert(root, x); //root is the root of the tree (private variable) } – Abhishek Ranjan Oct 05 '15 at 06:11
  • @user657267 but why does it work if the root is non-null? shouldn't then its children pointers also stay null as I insert more, since I am not passing it by reference? – N. Gupta Oct 05 '15 at 06:15
  • @AbhishekRanjan thanks, I figured that out, my question is why this method fails if the root is null. Since it doesn't pass by reference (as user657267 pointed out), shouldn't its children also remain null as I insert more? – N. Gupta Oct 05 '15 at 06:17
  • If you look to your code , A node is made but the root is not made to point to it. The root remains null, so the BST is essentially empty. Hope this helps. – Abhishek Ranjan Oct 05 '15 at 06:22
  • @AbhishekRanjan aaah now i get it! Thanks! – N. Gupta Oct 05 '15 at 06:27
  • @N.Gupta `cur` itself is a copy of a pointer in your code, but whatever it points to is still modified if you dereference it, i.e. `*cur` and `*root` will return the same object. – user657267 Oct 05 '15 at 06:37

0 Answers0