Why a lot of binary-tree data structures in C do not have a parent node pointer?

Question

I'm new to C programming, and I'm learning C algorithms with C.

Here is my problem about how to define the binary tree node data structure.

Use or NOT use a parent node pointer

Here are 2 typical sample code for defining a Node data structure.

Without parent node pointer

typedef struct binaryTreeNode_{
  int key;
  void *data;
  binaryTreeNode_ *leftNode;
  binaryTreeNode_ *rightNode;
} binaryTreeNode;

With parent node pointer

typedef struct binaryTreeNode_{
  int key;
  void *data;
  binaryTreeNode_ *leftNode;
  binaryTreeNode_ *rightNode;
  binaryTreeNode_ *parentNode;
} binaryTreeNode;

My question

Obviously, using a node structure with a parent node pointer will make a lot of work much more easier. Like traverse a node/a tree, DFS/BFS with binary tree. So my question is why there are some solutions that are based on a structure without parent node?.

Are there any historical reasons? If simply because the limitation of RAM/DISK capacity, I think we can drop the solution that does not have a parent node, can't we?

Maybe not relavent

Just like Linked List and Doubly Linked List, should we use Doubly Linked List to implement Stack and Queue?

Answer 1

There are very good reasons to use a tree without parent pointers, and memory usage isn't the issue.

In the functional programming world (think Lisp, Scheme, Standard ML, OCaml, Haskell, F#, and so on), trees and linked lists are very common data structures, so even in C a lot of thinking about trees and lists is influenced by FP. Trees and lists are recursively defined (a tree is either a leaf or an interior node whose children are trees, and a list is either nil or a node with a data element and a list attached), and they are almost always implemented as immutable datastructures. Immutability is helpful because it makes parallelism cleaner (no programmer-visible locks), sharing of data between functions nicer (don't have to copy data), and proofs easier.

The problem with a parent pointer or a doubly linked list is that suddenly immutability goes out the window. With an immutable object, you have to specify everything about the object at time of creation. So, if you want to maintain immutability, you can't create a node until its children have been created (because those children have to be specified at the time of creation), but you also can't set parent pointers on the children before the parent has been created (because the parent doesn't exist). In other words, immutability does not play well with circular dependencies. Similarly, you can't create a doubly linked list without some mutation, since without mutation you can't create the first node until the second node has been created, and you can't set the previous pointer on the second node until the first node has been created.

The FP folks manage to write a lot of code with strictly immutable datastructures, and prove lots of useful properties to boot. Certainly, maintaining parent pointers makes the programmer's life more difficult, because as soon as you change one node in the tree you have to make changes to all its children's parent pointers, which is a pain.

Because so much thinking on lists and trees has been influenced by FP, which doesn't include parent pointers or doubly linked lists, and because maintaining parent pointers is a tricky business likely to introduce bugs, many C tree implementations don't use parent pointers.

---

Also, one other note: you ask about using linked lists versus doubly linked lists for stacks and queues. There is no need to use a doubly linked list to implement a stack, because you don't need efficiency in traversing any element but the first (and the second, if the stack is mutable). There is a cute trick to implement a queue with two stacks, which provides amortized constant time queue operations. If you're not using that, though, a queue is also a decent use case for either a doubly linked list or an array.

Answer 2

A tree rarely requires a parent pointer for the regular/simple operations. It is only when you are doing something exotic (say retracing the path back from a leaf to a node) that a parent pointer maybe required.

Are there any historical reasons? If simply because the limitation of RAM/DISK capacity, I think we can drop the solution that does not have a parent node, can't we?

Some historical reasons too. Also, memory constraints would require you to use the smallest, most compact structures. Even to this day, there are embedded systems with stringent memory requirements. Also, you wouldn't really want to mess with existing code that works, so these things stick.

So my question is why there are some solutions that are based on a structure without parent node?

Possibly because their applications did not require accessing the parent that often. Note, that this is a typical space-time tradeoff.

Just like Linked List and Doubly Linked List, should we use Doubly Linked List to implement Stack and Queue?

That depends on your application and the gurantees your data structures need to provide per operation. Also, you may be interested in looking up the XOR linked list!