CODEWITHSUNDEEP
c++smart-pointers
Mr.Mips
Mr.Mips

Reputation: 399

Creating a smart pointer in a struct?

I'm modeling a Node in a Binary Tree using a struct. In the struct, I'm trying to have a pointer to the left and right child.

The problem is, I keep running into a stack overflow due to the way I'm creating the struct. It seems the way I've been handling the smart pointers continuously allocates memory on the stack.

The exception is specifically thrown when I create theroot in my main.

I'm new to smart pointers (I've been using raw pointers which I have recently learned is bad practice in C++), and I have tried solving this issue on my own without luck.

Can someone critique my struct/smart pointer use? Many thanks. 

#include <iostream> 
#include <memory> 

//Node struct 
struct Node
{
    int data;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;

    Node(int data) {
        this->data = data;
        this->left = std::make_unique<Node>(NULL);
        this->right = std::make_unique<Node>(NULL); 
    }

};

//insert Node into binary search tree
void insert(int data, std::unique_ptr<Node>& root)
{
    if (root == NULL)
    {
        root = std::make_unique<Node>(data);
    }
    else {
        if (root->data > data)
        {
            insert(data, root->left);
        }
        else {
            insert(data, root->right);
        }
    }
}

//In Order tree traversal 
void inOrderTraversal(std::unique_ptr<Node>& root)
{
    if (root == NULL) return; 

    inOrderTraversal(root->left); 

    std::cout << root->data << std::endl; 

    inOrderTraversal(root->right); 
}

int main()
{
    //Initialize root to NULL
    std::unique_ptr<Node> root = std::make_unique<Node>(NULL);


    insert(20, root); 
    insert(50, root);
    insert(30, root);
    insert(5, root);
    insert(6, root);
    insert(99, root);
    insert(77, root);
    insert(56, root);
    insert(32, root);
    inOrderTraversal(root); 

    return 0; 
}

Upvotes: 1

Views: 1423

Answers (2)

Kostas
Kostas

Reputation: 4176

The function std::make_unique<Node> takes parameters to forward the Node constructor.

In C and C++ NULL is usually just a macro for 0.

Therefore, when you call std::make_unique<Node>(NULL); you are initializing a Node, using data = 0.

This then recursively calls this->left = std::make_unique<Node>(NULL);, causing infinite recursion and stack overflow eventually.

To solve this you can assign std::unique_ptr<Node> left = NULL.

I would also suggest using nullptr in the place of NULL because it is type safe. Simply replacing NULL with nullptr on your code gives compiler errors, helping you resolve the issue.

error: no matching constructor for initialization of 'Node'

Upvotes: 2

ObliteratedJillo
ObliteratedJillo

Reputation: 5166

Replace all NULL with nullptr and don't use std::make_unique(NULL);

Node::Node(int data) {
    this->data = data;
    this->left = nullptr;
    this->right = nullptr;
}



int main()
{
    //Initialize root to NULL
    std::unique_ptr<Node> root = nullptr;

        // other codes ..
}

Upvotes: 1

Related Questions