Smart Pointers for Binary Tree [closed]

Question

If I have a binary tree where each node contain just pointers to children nodes, then unique_ptr works very well. If I want each node to have a parent pointer, then the situation is not so nice, since a node may have three pointers pointing to it: Binary Tree with parent pointer

What can I do in this instance? I can use shared_ptr for everything, but I've been told it's not a good design since I may get cycles. If I were to use a weak_ptr for the parent pointer, which shared_ptr do I create this weak_ptr from?

Which types of pointers would be a good fit for a binary tree?

Answer 1

If I have a binary tree where each node contain just pointers to children nodes, then unique_ptr works very well.

Right.

If I want each node to have a parent pointer, then the situation is not so nice, since a node may have three pointers pointing to it

You should distinguish pointers between owning pointers and observing pointers.

Having raw owning pointers is a bad idea and a source of bugs and leaks; on the other hand, having raw observing pointers can be fine in many cases (as long as the observed object is still "live").

In your case, you may want to consider a design in which each node contains unique_ptrs to children nodes, as these are owning pointers, and using a smart owning pointer like unique_ptr works well in this case.

On the other hand, the children nodes can refer to their parent using a non-owning pointer (the children "don't own" their parent, the children nodes just observe their parent), and a raw pointer works fine as non-owning observing pointer.

As a side note, when/if you use shared_ptr you have to pay attention to cycles, as if you don't properly break them, then you have leaks (unreleased objects). On the other hand, the parent pointing to children via owning unique_ptrs, and the children observing their parent via raw observing pointers, seems a simpler design to me.