6_Trees_ Recursive Version To count Number of Nodes in BT

5_Tracing Recursion on Trees

In this Topic we will learn how to Traverse a trees using recursion !

Recall that we have used stack activation method to traverse the output of a recursive tree calls but don't you think that t is very lengthy to trace out the output on trees.

So lets introduce you with one another method of analyzing Recursion program on Trees

Key point - Whenever there are more number of statements in your recursive program we shall use following method and this method will be applicable to trace out all types of recursive programs on trees ADT




https://drive.google.com/file/d/1wMeRF5r_lr-d-eBiZcSdruipy1iiHFun/view?usp=sharing

4_Construction of Unique Binary Trees

https://drive.google.com/file/d/1PVQr4gV-NsPX9ZXDzy_NA4FDAptFi9pZ/view?usp=sharing



https://drive.google.com/file/d/1WQPL4m4Xj5eg7c_jlmOvXV1qh1fL6pU3/view?usp=sharing



Example


https://drive.google.com/file/d/1TEzgjahi__WigaI-XeYYBufYx1igppk9/view?usp=sharing

2_Trees Traversal

In this Unit we will Learn about Trees ADT and how to Implement them

Why to use Tree ADT. Theoretical understanding regarding its time has already been seen why we are using trees! Remember the time complexity in searching log (n) over the cost of insertion and deletion (o(n) ) . Have you observed on your computer how files are organized in a tree structure?

Fine!

Observe some other interesting applications of Trees!

Now let's start this journey by finding different possibilities with which we can make trees

See there are two scenarios - 1) if you are given some nodes without labels and 

                                               2) with labels

can you draw a number of binary trees possible in each case?

A binary tree is one which is having a degree of at most 2, thus nodes with degrees 0,1,2 are binary  

1_Trees basics

Tree
In this unit Let me briefly tell you why we are studying this ADT

As you know that Searching an element using in a linked list takes ~0(n) time. How?

 Let's assume that you wish to search an element named "A"  in a given linked list ( Obviously LL is a data Structure) that contains elements  A,B,D,E . What will be the worst case  ( This is when The Element is placed at the last in the linked list) so how much time it will take to search this A now, Obviously you have to traverse each element and then you will be able to find A ., How many elements are there in the list ? 4 here , so if elements are n then how much time you will take in worst case = ~0(n). Fine!

Now if we can reduce this time to some Log time Don't you think it is more wonderful ?

How, Lets use the concept of one more non linear ADT called Trees. A tree is a non linear  structure in which each node is connected with some other node (forming parent child relationship) to form a hierarchical structure.  the point is to reduce the searching time !

But even before that lets try to understand different types of trees with their terminologies !

1. We have discussed linear data structures, such as, Arrays, Strings, Stacks, and Queues. 
2. Now, we will learn about a Non-Linear Data Structure called TREE.
3. A tree is a structure which is mainly used to store data that is hierarchical in nature. First, we will understand general trees and then Binary Trees. 
4. These binary trees are used to form binary search trees and heaps. They are widely used to manipulate Arithmetic Expressions, Construct Symbol Tables, and for Syntax Analysis.

Now Hope you understood The definition ! Please keep in mind that some books follow slightly different conventions while defining the  types of trees.

Now lets try to explore why the complexity turns out to be logn in searching for an element 

A) Best Time complexity - element is present at root = O(1)

B) Average Time Complexity in BST

There n is number of nodes in binary tree, if suppose you have n= 8 , then log(8)= 3 , i.e you need to process 3 levels in order to find any element.  

But ! wait what if the tree is skewed !


C) And worst-case complexity is when tree is skewed

So, What will be the advantage of using trees if their complexity turns out to be ~0(n); Yes you are right there is no advantage if the tree is skewed but if it is complete or almost complete than you can take logn time advantage over ~o(n). Ok!



Hope You are now clear about the different terminologies used in Trees ! and the reason we are using this ADT


But wait I know that you reduced the time by using Trees but it is on the cost of inserting and deletion ! in Trees both operation involves traversing a node and then deletion/insertion. So in the worst case, A node is present at last and thus you need to traverse all the nodes in order to reach that node.
If visiting a node takes a C amount then to visit n nodes will take ~=Cx o(n) =O()n

Conclusion - Trees reduces searching (log (n) , in linked list = O(n)) but insertion and deletion time increases that is = O(n)  which is O(1) in case of lionked list. 

3_Tree Traversals Lab

/******************************************************************************

Trees Concepts !   Inoder Traversal              
@Mukesh Mann dated 23-03-2020

*******************************************************************************/
/******************************************************************************
*******************************************************************************/
#include <stdio.h>

 typedef struct node

            {

                int data;

                struct node *left;

                struct node *right;

             

            }Node;



// Lets try to creat a root node first

int * create()

{

 

 int x;

Node *newnode=(Node*)malloc(sizeof(Node));

 printf("Enter the data for the nodes(-1 for no data)");



 scanf("%d", &x);



 if(x==-1)

 {

     //printf("You have not entered any data");

     return NULL;

      }

      newnode->data=x;

      printf("Enter the left child data rooted at %d \n",newnode->data);

      newnode->left=create();

      printf("Enter the right child data rooted at %d\n",newnode->data);

      newnode->right=create();

      return newnode;

 

}

void traverse(Node *t)

{

 

    if(!t==NULL)

    {

   

     printf("Left child data is %d ",t->data);

      //printf("Left child data is %d",t->left->data);

      //printf("right child data is %d",t->left->data);

       traverse(t->left);

       t=t->right;

      }

   

   if(!t==NULL)

      {

       

       printf("Right child data is %d\n",t->data);

      //printf("Left child data is %d",t->left->data);

      //printf("right child data is %d",t->left->data);

       traverse(t->right);

       //t=root;

       

      }

}

void Inorder(Node *t)

{

    //printf("In order traversal is" );

    if(t)

    {

    Inorder(t->left);

    printf(" %d",t->data);

    Inorder(t->right);

     

    }

}



int main()

{

Node *root=create();

Node *t=root;

printf("Root child is %d\n ",t->data);

traverse(t);

Inorder(t);

printf(" is the order traversal \n\n" );


    return 0;

}

Data Structure- 5 Queue Concept using Circular Array

// In this article we will Learn concept of circular array to

implement the queue concept because as we can see the in linear array there is a no way to store new item even if there is a space after deleting an element ! 

with circular array w will use MAX-1 index of array and initially we will put front and rear to index zero position !

1. when we need to insert a data we just increment the rear and insert the data !
2. When we need to delete the data we just increase the front and print the data!

Only important point is that when during insertion if rear== front then it means the queue is full now and we will put rear one position back , if rear =0 then one position back is MAX-1; and if rear != 0 then one position back is rear-1;

In order to move rear and front we will use mod operator!

/******************************************************************************
Queue Concept using Circular Array !               
@Mukesh Mann dated 16-02-2020
*******************************************************************************/

#define MAX 4

enqueue(int);

//void delete();

void display();

int queue_array[MAX];

int rear = 0;

int front = 0;

 enqueue(int item)

{

    //int item;

     rear=(rear+1)%MAX;

    if (front==rear)

    {

        printf("Queue Overflow \n");

        if(rear==0)

        {

          rear=MAX-1; 

        }

        else {

        rear=rear-1;}

        return;

    }

    else

    {

    queue_array[rear]= item;

    printf("iTEM INSERTED is %d\n",queue_array[rear]);

       return;

    }

} /* End of Enqueue() */

 deqeue()

{

    if(front==rear)

    {

         printf("Queue is empty on");

         return -1;

    }

    else

    {

          front=(front+1)%MAX;

         int item= queue_array[front];

         printf("Deleted Item is %d\n",item);

          return item;

    }

  

} /* End of deqeue() */

 main()

 {

    

// Here we try to insert 3 item using a loop

 // initially front and rear are point to zero and we will utilize only max-1 index of circular array

     for (int i = front; i <= MAX-1; i++){

     enqueue(i);

      }

     

      for (int i = front; i <= MAX-1; i++){

       deqeue();

      }

    

}