Tonny Xu 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



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

Answer

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!

Comments