Binary tree implemented using references

Question

I implemented a binary tree using references because I couldn't see why people don't use references instead of pointers to implement data structures such as binary trees:

#include <iostream>
struct Node {
 Node(Node& l, Node& r, const char* v) : left_child(l), right_child(r), value(v) {}
 const char* value;
 Node& left_child;
 Node& right_child;
};
Node null_node(null_node, null_node, "END_OF_TREE");
bool is_leaf(Node& node){
 return &node.left_child == &null_node && &node.right_child == &null_node;
}
void post_order(Node& node){
 if (is_leaf(node)){
 std::cout << node.value;
 }
 else{
 if (&node.left_child != &null_node){
 post_order(node.left_child);
 }
 if (&node.right_child != &null_node){
 post_order(node.right_child);
 }
 std::cout << node.value;
 }
}
int main(){
 Node n1(null_node, null_node, "1");
 Node n2(null_node, null_node, "2");
 Node n3(n1, n2, "3");
 Node n4(null_node, null_node, "4");
 Node n5(n3, n4, "5");
 post_order(n5);
}

I still can't see why references are inferior to pointers. What's wrong with using references for binary tree (other than that you can't insert or delete elements)?

Also I'm completely new to C++ so any feedback on the code itself is appreciated as well. Thank you.

• πάντα ῥεῖ: The more questionable points are, why you are using 1. A fixed value type instead of a template 2. A char* value for representing a string.
• Loki Astari: 1. Reference are not inferior to pointers (they are better in a lot of cases). 2. We don't use them in trees because they can't be null (hard to find the leaf without null (your code will break if I create an alternative leaf node)). 3. You did not create a tree. You created a node class (that can be joined together like a tree but does not have to be). To make this a tree you need to enforce that it can not be any other shape. For this you need a tree class that uses node internally.
• Jerry Coffin: Asking: "What's wrong with using references for binary tree (other than that you can't insert or delete elements)?" is a little like asking: "what's wrong with carrying sand in your canteen (other than that you can't drink it)?" If it's not dynamic, you're probably better off with some other data structure.
• JDługosz: The difference is that you have to build the whole tree from the bottom up, and can't insert or delete afterwards.

Answer 1

What's wrong with using references for binary tree (other than that you can't insert or delete elements)?

Well, it does work, as you've shown. But in order to use references instead of pointers, you had to make two awkward changes to the "natural" pointer-based code:

(1) You had to invent a null_node object, which is a global variable, and suffers all the problems of global variables (for example, it won't play well with dynamic libraries, a.k.a. shared objects, a.k.a. DLLs, because you might end up with a program containing two null_node variables — one from the main program and one from the DLL).

(2) You had to prefix all your accesses with an extra & character.

Compare your way (slightly reformatted for style and const-correctness):

void post_order(const Node& node) {
 if (&node.left_child != &null_node) {
 post_order(node.left_child);
 }
 if (&node.right_child != &null_node) {
 post_order(node.right_child);
 }
 std::cout << node.value;
}

to the "natural" approach:

void post_order(const Node *node) {
 if (node->left_child) {
 post_order(node->left_child);
 }
 if (node->right_child) {
 post_order(node->right_child);
 }
 std::cout << node->value;
}

Which one is easier to read (and incidentally to write)?

Notice that C++'s syntax for pointers dates back all the way to C, i.e., the mid-1970s. It's had a long time to polish and refine and streamline that syntax. You're trying to invent something "better", without the benefit of controlling the language definition. You shouldn't be surprised that the built-in, ~40-year-old syntax is really suitable for the exact job it was designed for. :)

By the way, if you want to deal with empty trees in the "natural" way, consider the following refactoring:

void post_order(const Node *node) {
 if (node != nullptr) {
 post_order(node->left_child);
 post_order(node->right_child);
 std::cout << node->value;
 }
}

Straight-line code is best code!

Answer 2

While it's OK in principle to use references instead of pointers for the Node class, there's not much gain from it by means of type safety, or protection from usage of dangling object instances.

Think about a situation a client code uses new to create a node instance:

Node n1(null_node, null_node, "1");
Node* n2 = new Node(null_node, null_node, "2"); // Dynamically allocated for
 // whatever reason
Node n3(n1, *n2, "3");
// Some exception prone code here ...
Node n4(null_node, null_node, "4");
Node n5(n3, n4, "5");
post_order(n5);
delete n2;

Might leave you with a memory leak in case of an exception.

Also, if delete n2; is used prior of the binary tree instance n5 goes out of scope, there will be a dangling reference used in the tree.

A better choice than using raw pointers or references would be to use an appropriate smart pointer like e.g.

struct Node {
 Node(std::unique_ptr<Node> l, std::unique_ptr<Node> r, const char* v) 
 : left_child(l), right_child(r), value(v) {}
 const char* value;
 std::unique_ptr<Node> left_child;
 std::unique_ptr<Node> right_child;
};

which makes ownership semantically clear, and avoids to mess around with memory management.