# Representing Lists As Binary Trees in C

**Case 1:**

A list could be represented as a Binary Tree with all the list elements along with their information at the leaf nodes. For example, the linked list

->[A| ]->[B| ]->[C| ]-> ………[I| ] could be represented as following Binary Tree –

5 / \ 2 2 / \ / \ 1 2 1 1 / \ / \ / \ / \ A B 1 E F G H I / \ C D

The list elements are represented by alphabets and the numbers represent the number of list elements to the left of that node. The list elements are numbered according to their **inorder** traversal in the tree.

**C Routine to find Kth element of the above Tree represented list**

The algorithm would be as follows –

r = K; p = tree; /* tree is the root node*/ while(p ! a leaf){ if(r <= lcount) p = left(p); else{ r -= lcount; p = right(p); } } find = p;

**Case 2:**

Now consider a scenario where all list elements are at each node of an AC Binary Tree and list elements are placed or numbered according to their **inorder** traversal.

->[S| ]->[T| ]->[R| ]-> ………[E| ] could be represented as following Binary Tree –

6T / \4U8R / \ / \2T5C7U9E / \1S3R

Finding K^{th} element and deleting K^{th} element of such a list is very easy since it could be done along with the **inorder** traversal of such a tree. For example, we are to find the 8th element i.e R. Now, start inorder traversal from element 1. Set a counter to 1 and increment it as we proceed the traversal. While traversing, we check the counter with the value of K if they matches, we stop traversing and thus when counter = k = 8, we find the 8th element R. This could be implemented easily as a C routine for recursive inorder traversal of a Binary Tree.

**C Routine to find K ^{th} element of the above Tree represented list**

The algorithm would be as follows –

scanf("%d", &K); counter = 1; void intravfork(NODEPTR tree){ if(tree != NULL){ intravfork(p->left); /* traverse left subtree*/ printf("%d", p->info); /* visit root */ if(counter == K){ printf("\nThe %d element is %d", K, p->info); return; } counter++; intravfork(p->right);/* traverse rightsubtree*/ } }

**Note:** To Delete K^{th} element –

if(counter == K){ freenode(p); return; }