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

Question

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?

You can create an array of BTNode with sufficient elements and use it as memory pool, taking nodes from the array. — MikeCAT
– MikeCAT, Commented Jul 24, 2016 at 2:51
You could create a std::vector<BTNode> to hold all the nodes. I personally don't think that is necessary. I would simply do auto newNode = new BTNode(8); and then set the appropriate pointers. — Rudy Velthuis
– Rudy Velthuis, Commented Jul 24, 2016 at 2:54
What you were advised was probably to avoid managing new and delete yourself. There's actually nothing wrong with dynamic memory management — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Jul 24, 2016 at 2:54
Actually dynamic memory allocation is nothing to be afraid of. Just make sure to use RAII to release your memory correctly. I'd only try to avoid dynamic allocation, when performance is a big issue. Yet I only rarely need it. — cdonat
– cdonat, Commented Jul 24, 2016 at 7:26

Sam Varshavchik · Accepted Answer · 2016-07-24 02:53:16Z

3

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.

answered Jul 24, 2016 at 2:53

Sam Varshavchik

119k6 gold badges109 silver badges164 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

cdonat · Accepted Answer · 2016-07-24 07:38:56Z

0

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.

answered Jul 24, 2016 at 7:38

cdonat

2,82220 silver badges24 bronze badges

Comments

MichaelMoser · Accepted Answer · 2016-07-24 10:43:35Z

0

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.

edited Jul 24, 2016 at 10:43

answered Jul 24, 2016 at 9:46

MichaelMoser

3,5342 gold badges31 silver badges26 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related