Representation 1 - Multi walk treetypedef struct multiWalkTreeNode{  struct multiWalkTreeNode * parent;  void *item;  struct multiWalkTreeNode **childPointer;}Node;typedef struct multiWalkTree{  Node *root;  int size; /*Number of nodes in the tree*/}Tree;Pictorial view:Representation 2 - LCRS treetypedef struct SiblingTreeNode{  struct SiblingTreeNode *parent;  void *item;  struct SiblingTreeNode *firstChild;  struct SiblingTreeNode *nextSibling;}Node;typedef struct LCRSTree{  Node *root;  int size;}Tree;Pictorial view:Representation 3 - Tree using list(How to name this tree?)typedef struct DListNode{  int item;  struct DListNode *next;  struct DListNode *prev;}DListNode;typedef struct DList{ //Circular  DListNode *head;  int size;}List;typedef struct treeNode{  struct treeNode *parent;  void * item;  List *childList;  /* Sentinel node is created on initial construction of a List */}Node;typedef struct treeUsingList{  Node *root;  int size;}Tree;Pictorial view:Parent pointer is introduced to perform DFS without recursion or explicit stack.Please confirm the correctness of representation.Question:1) Do we have any name for tree in Representation 3?2) For insert/delete/find operations, which representation performs better?3) Are there any other representations for rooted tree, that can enhance performance?
Rooted tree - Representation & Performance
c;data structures;trees
Here are some considerations:In #1, you aren't capturing a size of the childPointer array, so you cannot know how many children there are.Your code for #3 uses void *item in the text, but Node *item in the diagram.  Further, the items labeled sentinel have (struckthru) item, next and prev, but should (to match the text) have head and size .None of these data structures are optimized for find operations, so among these, the fewer data structures the better, within a small margin (as none is great for find).  If find is the primary concern I'd move to a totally different data structure (e.g. B-Tree or balanced binary tree, or anything else)!The #3 choice, I see as basically broken.  It uses a doubly linked list, which at first blush might imply some improvement for large numbers of children regarding insert/delete.  However, observe that the parent pointers from the nodes only refer to other tree nodes, and not also to the position in the doubly linked list (which themselves do not offer a parent pointer).  So a full traversal of immediate children is still necessary, just like in option #2, and, the doubly linked list offers no improvement, just more maintenance required and space taken (all bad).Workload is going to be the primary concern here regarding which is best for performance.  Regular trees (not one of your options) would be the best for insertion if there are, say, two or fewer children.  For huge numbers of children, a doubly linked list might be better, but not if implemented as #3.