CODEWITHSUNDEEP
c++binary-treedynamic-memory-allocation
Coffee Maker
Coffee Maker

Reputation: 1573

How do you create a pointer-based binary tree without using dynamic memory allocation?

Some C++ programmers say that dynamic memory allocation is bad and should be avoided whenever possible. I tried making a binary tree data structure without using dynamic memory allocation, and it doesn't work. Here's what I tried:

struct BTNode {
    BTNode *left = 0, *right = 0;
    int data;

    BTNode(int d_) { data = d_; }

    void insert(int d_) {
        BTNode n(d_);
        if (d_ <= data)
            if (left == 0) left = &n;
            else left->insert(d_);
        else 
            if (right == 0) right = &n;
            else right->insert(d_);
    }
}

And then doing this in main...

BTNode root(8);
root.insert(9);
root.insert(10);
cout << root.right->right->data;

results in a segfault, because the BTNode containing the data went out of scope a long time ago.

My question is, how is one supposed to structure a pointer-based binary tree like this without the use of new and delete?

Upvotes: 3

Views: 2281

Answers (3)

MichaelMoser
MichaelMoser

Reputation: 3500

The insert method is allocating the BTNode object on the stack, that means the object's memory is invalid once the insert function returns.

You could do

       BTNode newObj( 9 ) 
       root.insert( newObj );

You would also have to modify the insert method to

       void insert(BTNode &node) { ...

in this case newObj object remains in scope until you leave your main function. Even better you can make it of static scope, then it will be around for the duration of the program.

Upvotes: 0

cdonat
cdonat

Reputation: 2822

You can have all your nodes in a single std::array<>. They can freely point to each other an when you release your array, all your nodes are safely released as well. You just have to make sure to know which elements in your array have already been used.

Any way, please only implement your own trees and similar containers for educational reasons, or if you have very, very, very good reasons not to use the ones provided by the standard library. In the latter case, mimic the standard interface as closely as possible in order to enable standard algorithms, range based for-loops, and easily understandable code for other C++ developers.

Upvotes: 0

Sam Varshavchik
Sam Varshavchik

Reputation: 118425

The short answer is: you pretty much can't.

The only possible way is for the entire tree to be in either automatic, or global scope, and constructed manually:

BTNode root;
BTNode left, right;

root.left=&left;
root.right=&right;

But, either the whole thing gets destroyed, when the automatic scope is left, or you now have a bunch of ugly globals.

There's nothing wrong with dynamic scope, and dynamic memory allocation; provided that it's used correctly.

Upvotes: 3

Related Questions