Tonny Xu - 1 month ago 10
C Question

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

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

`Stack`
and
`Queue`
?

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!