EPI Version 2.1.0 - C++ - Chapter 9 - Binary Tree Node Struct - Pointer Mixing

#1

Hi EPI,

The BinaryTreeNode struct provided on page 132 is implemented using unique_ptr for both left and right children, and does not contain a parent pointer.

When a parent pointer is required as in problem 9.4 (Compute the LCA when nodes have parent pointers), the solution mixes raw pointers with smart pointers which can be a bit tricky.

My question is why not implement the Binary Tree Node struct with shared pointers (shared_ptr) especially if you include left, right, and parent pointers in the struct?

0 Likes
#2

Hi @kolaworld,

That is a good idea from what it looks like but the problem of using shared_ptr with parent will cause cyclic reference; such thing is bad as both parent and child are referencing each other so none of both will be freed eventually.

Let me know if you have any question, and this is definitely a very good question for sure.

0 Likes
#3

Hi @tsunghsienlee,

The issue with cyclic references makes sense. Could weak_ptr’s be used in place of raw pointers for parent pointer? Granted you would have to convert weak_ptrs to shared_ptr and then check for null before using, which adds complexity.

Also, the issue of cyclic references would come up for doubly linked lists or even a cyclic singly linked list, if using shared_ptrs exclusively. In an interview, would it be safer to simply implement linked list node/ binary tree node using only raw pointers and implement a destructor?

0 Likes
#4

Hi @kolaworld,

Using weak_ptr is definitely a good idea here. I don’t know the existence of this before until recently. In this scenario, weak_ptr is definitely suitable in this situation.

In interview, I would prefer using raw pointer directly since it is conveniently to write. The issue about cyclic reference in cyclic singly linked list, it is more like users already know this and where the cycle happens so the cyclic reference can be break easily. However, the cyclic reference in the binary tree case we are discussing can be easily prevented by using weak_ptr or raw_ptr so I would prefer this instead.

0 Likes