Loading....
Coupon Accepted Successfully!

 

Question 1

Write a C program to find the depth or height of a tree.
 


Here is some C code to get the height of the three


tree_height(mynode *p)
{
   if(p==NULL)return(0);
   if(p->left){h1=tree_height(p->left);}
   if(p=>right){h2=tree_height(p->right);}
   return(max(h1,h2)+1);




The degree of the leaf is zero. The degree of a tree is the max of its element degrees. A binary tree of height n, h > 0, has at least h and at most (2^h -1) elements in it. The height of a binary tree that contains n, n>0, elements is at most n and atleast log(n+1) to the base 2.

Log(n+1) to the base 2 = h

n = (2^h - 1)

 

Question 2

Write a C program to determine the number of elements (or size) in a tree.
 


Try this C program


int tree_size(struct node* node) 

  if (node==NULL) 
  { 
    return(0); 
  } 
  else 
  { 
    return(tree_size(node->left) + tree_size(node->right) + 1); 
  } 



Question 3

Write C code to check if a given binary tree is a binary search tree or not?
 


Here is a C program which checks if a given tree is a Binary Search Tree or not...


int isThisABST(struct node* mynode) 

    if (mynode==NULL) return(true); 
    if (node->left!=NULL && maxValue(mynode->left) > mynode->data) 
       return(false);
    if (node->right!=NULL && minValue(mynode->right) <= mynode->data) 
       return(false); 
    if (!isThisABST(node->left) || !isThisABST(node->right)) 
       return(false); 

    return(true); 



Question 4

Write C code to implement level order traversal of a tree.
 


If this is the tree,


        1
   2         3
 5   6     7   8



its level order traversal would be


1 2 3 5 6 7 8



You need to use a queue to do this kind of a traversal


Let t be the tree root.
while (t != null)
{
  visit t and put its children on a FIFO queue;
  remove a node from the FIFO queue and
  call it t;
  // Remove returns null when queue is empty
}




Pseduocode


Level_order_traversal(p)
{
   while(p)
   {
     Visit(p);
     If(p->left)Q.Add(p->left);
     If(p->right)Q.Add(p->right);
     Delete(p);
   }
}







Here is some C code (working :))..


#include 

typedef struct node
{
  int value;
  struct node *right;
  struct node *left;
}mynode;

mynode *root;

add_node(int value);

void levelOrderTraversal(mynode *root);

int main(int argc, char* argv[])

  root = NULL;
  
  add_node(5);
  add_node(1);
  add_node(-20);
  add_node(100);
  add_node(23);
  add_node(67);
  add_node(13);
  

  printf("\n\n\nLEVEL ORDER TRAVERSAL\n\n");
  levelOrderTraversal(root);
  
  getch();
}




// Function to add a new node...
add_node(int value)
{
   mynode *prev, *cur, *temp; 
   
   temp        = (mynode *) malloc(sizeof(mynode));
   temp->value = value;
   temp->right = NULL;
   temp->left  = NULL;

   if(root==NULL)
   {
     printf("\nCreating the root..\n");
     root = temp;
     return;
   }

   prev=NULL;
   cur=root;

   while(cur!=NULL)
   {
      prev=cur;
      cur=(valuevalue)?cur->left:cur->right;
   }

   if(value value)
     prev->left=temp;
   else
     prev->right=temp;
}



// Level order traversal..
void levelOrderTraversal(mynode *root)
{
  mynode *queue[100] = {(mynode *)0}; // Important to initialize!
  int size = 0;
  int queue_pointer = 0;
  
  while(root)
  {
      printf("[%d] ", root->value);

      if(root->left)
      {
        queue[size++] = root->left;
      }

      if(root->right)
      {
        queue[size++] = root->right;
      }
      
      root = queue[queue_pointer++];    
  }
}



Question 5

Write a C program to delete a node from a Binary Search Tree?
 


The node to be deleted might be in the following states
 

  • The node does not exist in the tree - In this case you have nothing to delete.
  • The node to be deleted has no children - The memory occupied by this node must be freed and either the left link or the right link of the parent of this node must be set to NULL.
  • The node to be deleted has exactly one child - We have to adjust the pointer of the parent of the node to be deleted such that after deletion it points to the child of the node being deleted.
  • The node to be deleted has two children - We need to find the inorder successor of the node to be deleted. The data of the inorder successor must be copied into the node to be deleted and a pointer should be setup to the inorder successor. This inorder successor would have one or zero children. This node should be deleted using the same procedure as for deleting a one child or a zero child node. Thus the whole logic of deleting a node with two children is to locate the inorder successor, copy its data and reduce the problem to a simple deletion of a node with one or zero children.



Here is some C code for these two situations


Situation 1


     100 (parent)

   50 (cur == psuc)

20    80 (suc)

         90

       85  95





Situation 2

           100 (parent)

        50 (cur)

     20    90
         
         80
        
       70 (suc)
         
          75
 
        72   76
          







mynode *delete(int item, mynode *head)
{
     mynode *cur, *parent, *suc, *psuc, q;

     if(head->left==NULL){printf("\nEmpty tree!\n");return(head);}

     parent = head;
     cur    = head->left;

     while(cur!=NULL && item != cur->value)
     { 
         parent  =  cur;
         cur     =  (item next)? cur->left:cur->right;
     }

     if(cur == NULL)
     {
        printf("\nItem to be deleted not found!\n");
        return(head);
     }


     // Item found, now delete it

     if(cur->left == NULL)
         q = cur->right;
     else if(cur->right == NULL)
         q = cur->left;
     else
     {
           // Obtain the inorder successor and its parent
          
           psuc = cur;
           cur  = cur->left;
 
           while(suc->left!=NULL)
           {
               psuc = suc;
               suc  = suc->left;
           }


           if(cur==psuc)
           {
                // Situation 1

                suc->left = cur->right;
           }
           else
           {
                // Situation 2

                suc->left  = cur->left;
                psuc->left = suc->right;
                suc->right = cur->right;
           }

           q = suc;

     }


     // Attach q to the parent node

     if(parent->left == cur)
        parent->left=q;
     else
        parent->rlink=q;

     freeNode(cur);

     return(head);
}



Question 6

Write C code to search for a value in a binary search tree (BST).
 


Here are a few C programs....


mynode *search(int value, mynode *root)
{
   while(root!=NULL && value!=root->value)
   {  
     root = (value value)?root->left:root->right;
   }
   
   return(root);
}




Here is another way to do the same


mynode *recursive_search(int item, mynode *root)
{
  if(root==NULL || item == root->value){return(root);}
  if(iteminfo)return{recursive_search(item, root->left);}
  return{recursive_search(item, root->right);}
}



Question 7

Write C code to count the number of leaves in a tree
 


Here is a C program to do the same...


void count_leaf(mynode *root)
{
   if(root!=NULL)
   {
      count_leaf(root->left);
      
      if(root->left == NULL && root->right==NULL)
      { 
        // This is a leaf!
        count++;
      }

      count_leaf(root->right);
   }
}



Question 8

Write C code for iterative preorder, inorder and postorder tree traversals
 


Here is a complete C program which prints a BST using both recursion and iteration. The best way to understand these algorithms is to get a pen and a paper and trace out the traversals (with the stack or the queue) alongside. Dont even try to memorize these algorithms!


#include 

typedef struct node
{
  int value;
  struct node *right;
  struct node *left;
}mynode;

mynode *root;

add_node(int value);
void postorder(mynode *root);
void inorder(mynode *root);
void preorder(mynode *root);

void iterativePreorder(mynode *root);
void iterativeInorder (mynode *root);
void iterativePostorder(mynode *root);


int main(int argc, char* argv[])

  root = NULL;
  
  add_node(5);
  add_node(1);
  add_node(-20);
  add_node(100);
  add_node(23);
  add_node(67);
  add_node(13);
  
  printf("\nPreorder (R)    : ");
  preorder(root);
  printf("\nPreorder (I)    : ");
  iterativePreorder(root);

  printf("\n\nPostorder (R)   : ");
  postorder(root);
  printf("\nPostorder (R)   : ");
  iterativePostorder(root);
  
  
  printf("\n\nInorder (R)     : ");
  inorder(root);
  printf("\nInorder (I)     : ");
  iterativeInorder(root);

}

// Function to add a new node to the BST
add_node(int value)
{
   mynode *prev, *cur, *temp; 
   
   temp        = (mynode *) malloc(sizeof(mynode));
   temp->value = value;
   temp->right = NULL;
   temp->left  = NULL;

   if(root==NULL)
   {
     printf("\nCreating the root..\n");
     root = temp;
     return;
   }

   prev=NULL;
   cur=root;

   while(cur!=NULL)
   {
      prev=cur;
      cur=(valuevalue)?cur->left:cur->right;
   }

   if(value value)
     prev->left=temp;
   else
     prev->right=temp;
}


// Recursive Preorder
void preorder(mynode *root)
{
  if(root)
  {
    printf("[%d] ", root->value);
    preorder(root->left);
    preorder(root->right);
  }
}

// Iterative Preorder
void iterativePreorder(mynode *root)
{
  mynode *save[100];
  int top = 0;

  if (root == NULL)
  {
    return;
  }
  
  save[top++] = root;
  while (top != 0) 
  {
    root = save[--top];

    printf("[%d] ", root->value);

    if (root->right != NULL)
      save[top++] = root->right;
    if (root->left != NULL)
      save[top++] = root->left;
  }
}

// Recursive Postorder
void postorder(mynode *root)
{
  if(root)
  {
    postorder(root->left);
    postorder(root->right);
    printf("[%d] ", root->value);
  }
}

// Iterative Postorder
void iterativePostorder(mynode *root)
{
  struct 
  {
    mynode *node;
    unsigned vleft :1;   // Visited left?
    unsigned vright :1;  // Visited right?
  }save[100];
  
  int top = 0;
  
  save[top++].node = root;

  while ( top != 0 ) 
  {
      /* Move to the left subtree if present and not visited */
      if(root->left != NULL && !save[top].vleft) 
      {
          save[top].vleft = 1;
          save[top++].node = root;  
          root = root->left;
          continue;
      }

      /* Move to the right subtree if present and not visited */
      if(root->right != NULL && !save[top].vright ) 
      {
          save[top].vright = 1;
          save[top++].node = root;
          root = root->right;
          continue;
      }
    
      printf("[%d] ", root->value);

      /* Clean up the stack */
      save[top].vleft = 0;
      save[top].vright = 0;

      /* Move up */
      root = save[--top].node;
   }
}


// Recursive Inorder
void inorder(mynode *root)
{
  if(root)
  {
    inorder(root->left);
    printf("[%d] ", root->value);
    inorder(root->right);
  }
}


// Iterative Inorder..
void iterativeInorder (mynode *root)
{
  mynode *save[100];
  int top = 0;

  while(root != NULL) 
  {
      while (root != NULL) 
      {
           if (root->right != NULL)
           {
             save[top++] = root->right;
           }
           save[top++] = root;
           root = root->left;
      }
    
      root = save[--top];
      while(top != 0 && root->right == NULL) 
      {
          printf("[%d] ", root->value);
          root = save[--top];
      }
    
      printf("[%d] ", root->value);
      root = (top != 0) ? save[--top] : (mynode *) NULL;
  }
}




And here is the output...


Creating the root..

Preorder (R)    : [5] [1] [-20] [100] [23] [13] [67]
Preorder (I)    : [5] [1] [-20] [100] [23] [13] [67]

Postorder (R)   : [-20] [1] [13] [67] [23] [100] [5]
Postorder (R)   : [-20] [1] [13] [67] [23] [100] [5]

Inorder (R)     : [-20] [1] [5] [13] [23] [67] [100]
Inorder (I)     : [-20] [1] [5] [13] [23] [67] [100]



Question 9

Can you construct a tree using postorder and preorder traversal?
 


No

Consider 2 trees below



Tree1

  a



Tree 2

a
  b


preorder  = ab 
postorder = ba 



Preorder and postorder do not uniquely define a binary tree. Nor do preorder and level order (same example). Nor do postorder and level order.

Question 10

Construct a tree given its inorder and preorder traversal strings. Similarly construct a tree given its inorder and post order traversal strings.
 


For Inorder And Preorder traversals


inorder  = g d h b e i a f j c
preorder = a b d g h e i c f j



Scan the preorder left to right using the inorder sequence to separate left and right subtrees. For example, "a" is the root of the tree; "gdhbei" are in the left subtree; "fjc" are in the right subtree. "b" is the next root; "gdh" are in the left subtree; "ei" are in the right subtree. "d" is the next root; "g" is in the left subtree; "h" is in the right subtree.




For Inorder and Postorder traversals

Scan postorder from right to left using inorder to separate left and right subtrees.


inorder   = g d h b e i a f j c
postorder = g h d i e b j f c a



Tree root is "a"; "gdhbei" are in left subtree; "fjc" are in right subtree.



For Inorder and Levelorder traversals

Scan level order from left to right using inorder to separate left and right subtrees.



inorder     = g d h b e i a f j c
level order = a b c d e f g h i j



Tree root is "a"; "gdhbei" are in left subtree; "fjc" are in right subtree.


Here is some working code which creates a tree out of the Inorder and Postorder
traversals. Note that here the tree has been represented as an array. This really simplifies the whole implementation.

Converting a tree to an array is very easy

Suppose we have a tree like this


      A
  B       C
 D E     F G



The array representation would be


a[1] a[2] a[3] a[4] a[5] a[6] a[7]
  A    B    C    D    E    F    G



That is, for every node at position j in the array, its left child will be stored at position (2*j) and right child at (2*j + 1). The root starts at position 1.




// CONSTRUCTING A TREE GIVEN THE INORDER AND PREORDER SEQUENCE

#include
#include
#include

/*-------------------------------------------------------------
* Algorithm
*
* Inorder And Preorder
* inorder = g d h b e i a f j c
* preorder = a b d g h e i c f j
* Scan the preorder left to right using the inorder to separate left
* and right subtrees. a is the root of the tree; gdhbei are in the
* left subtree; fjc are in the right subtree.
*------------------------------------------------------------*/

static char io[]="gdhbeiafjc";
static char po[]="abdgheicfj";
static char t[100][100]={'\0'};  //This is where the final tree will be stored
static int hpos=0;

void copy_str(char dest[], char src[], int pos, int start, int end);
void print_t();

int main(int argc, char* argv[])
{
  int i,j,k;
  char *pos;
  int posn;

  // Start the tree with the root and its
  // left and right elements to start off

  for(i=0;i   {
     if(io[i]==po[0])
     {
        copy_str(t[1],io,1,i,i);             // We have the root here
        copy_str(t[2],io,2,0,i-1);           // Its left subtree
        copy_str(t[3],io,3,i+1,strlen(io));  // Its right subtree
        print_t();
     }
  }
 
  // Now construct the remaining tree
  for(i=1;i   {
     for(j=1;j<=hpos;j++)
     {
        if((pos=strchr((const char *)t[j],po[i]))!=(char *)0 && strlen(t[j])!=1)
        {
            for(k=0;k             {
               if(t[j][k]==po[i]){posn=k;break;}
            }
            printf("\nSplitting [%s] for po[%d]=[%c] at %d..\n", t[j],i,po[i],posn);

            copy_str(t[2*j],t[j],2*j,0,posn-1);
            copy_str(t[2*j+1],t[j],2*j+1,posn+1,strlen(t[j]));
            copy_str(t[j],t[j],j,posn,posn);
            print_t();
        }
     }
  }
}

// This function is used to split a string into three seperate strings
// This is used to create a root, its left subtree and its right subtree

void copy_str(char dest[], char src[], int pos, int start, int end)
{
  char mysrc[100];
  strcpy(mysrc,src);
  dest[0]='\0';
  strncat(dest,mysrc+start,end-start+1);
  if(pos>hpos)hpos=pos;
}


void print_t()
{
  int i;
  for(i=1;i<=hpos;i++)
  {
    printf("\nt[%d] = [%s]", i, t[i]);
  }
  printf("\n");
}




 




Test Your Skills Now!
Take a Quiz now
Reviewer Name