Loading....
Coupon Accepted Successfully!

 

Question 21

Write C code to determine if two trees are identical
 


Here is a C program using recursion


int identical(struct node* a, struct node* b) 

  if (a==NULL && b==NULL){return(true);} 
  else if (a!=NULL && b!=NULL) 
  { 
    return(a->data == b->data && 
           identical(a->left, b->left) && 
           identical(a->right, b->right)); 
  } 
  else return(false); 



Question 22

Write a C program to find the mininum value in a binary search tree.
 


Here is some sample C code. The idea is to keep on moving till you hit the left most node in the tree


int minValue(struct node* node) 

  struct node* current = node; 

  while (current->left != NULL) 
  { 
    current = current->left; 
  }
 
  return(current->data); 



On similar lines, to find the maximum value, keep on moving till you hit the right most node of the tree.

Question 23

Write a C program to compute the maximum depth in a tree?
 


Here is some C code...


int maxDepth(struct node* node) 

  if (node==NULL) 
  { 
    return(0); 
  } 
  else 
  { 
    int leftDepth  = maxDepth(node->left); 
    int rightDepth = maxDepth(node->right); 
    if (leftDepth > rightDepth) return(leftDepth+1); 
    else return(rightDepth+1); 
  } 



Question 24

Write a C program to create a mirror copy of a tree (left nodes become right and right nodes become left)!
 


This C code will create a new mirror copy tree.


mynode *copy(mynode *root)
{
  mynode *temp;
  
  if(root==NULL)return(NULL);
   
  temp = (mynode *) malloc(sizeof(mynode));
  temp->value = root->value;

  temp->left  = copy(root->right);
  temp->right = copy(root->left);

  return(temp);
}





This code will will only print the mirror of the tree



void tree_mirror(struct node* node) 

   struct node *temp;

   if (node==NULL) 
   { 
     return; 
   } 
   else 
   { 
      tree_mirror(node->left); 
      tree_mirror(node->right); 

      // Swap the pointers in this node 
      temp = node->left; 
      node->left = node->right; 
      node->right = temp; 
   } 



Question 25

Write C code to return a pointer to the nth node of an inorder traversal of a BST.
 


Here is a C program. Study it carefully, it has some Gotchas!


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

mynode *root;
static ctr;

void nthnode(mynode *root, int n, mynode **nthnode /* POINTER TO A POINTER! */);

int main()
{
  mynode *temp;
  root = NULL;
  
  // Construct the tree
  add(19);
  add(20);
  ...
  add(11);

  // Plain Old Inorder traversal 
  // Just to see if the next function is really returning the nth node?
  inorder(root);

  // Get the pointer to the nth Inorder node
  nthinorder(root, 6, &temp);

  printf("\n[%d]\n, temp->value);
  return(0);
}

// Get the pointer to the nth inorder node in "nthnode"
void nthinorder(mynode *root, int n, mynode **nthnode)
{
  static whichnode;
  static found;

  if(!found)
  {
    if(root)
    {
       nthinorder(root->left, n , nthnode);
       if(++whichnode == n)
       {
          printf("\nFound %dth node\n", n);
          found = 1;
          *nthnode = root; // Store the pointer to the nth node.
        }
       nthinorder(root->right, n , nthnode);
    }
  }
}


inorder(mynode *root)
{
  // Plain old inorder traversal
}


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

  if(root == NULL)
  {
    root = temp;
  }
  else
  {
    prev = NULL; 
    cur  = root;

    while(cur)
    {
      prev = cur;
      cur  = (value value)? cur->left : cur->right;
    }
  
    if(value > prev->value)
       prev->right = temp;
    else
       prev->left  = temp;
  } 
}   




There seems to be an easier way to do this, or so they say. Suppose each node also has a weight associated with it. This weight is the number of nodes below it and including itself. So, the root will have the highest weight (weight of its left subtree + weight of its right subtree + 1). Using this data, we can easily find the nth inorder node.


Note that for any node, the (weight of the leftsubtree of a node + 1) is its inorder rankin the tree!. Thats simply because of how the inorder traversal works (left->root->right). So calculate the rank of each node and you can get to the nth inorder node easily. But frankly speaking, I really dont know how this method is any simpler than the one I have presented above. I see more work to be done here (calculate thw weights, then calculate the ranks and then get to the nth node!).

Also, if (n > weight(root)), we can error out saying that this tree does not have the nth node you are looking for.

Question 26

Write C code to implement the preorder(), inorder() and postorder() traversals. Whats their time complexities?
 


Here are the C program snippets to implement these traversals...

Preorder


preorder(mynode *root)
{
  if(root)
  {
    printf("Value : [%d]", root->value);
    preorder(root->left);
    preorder(root->right);
  }
}



Postorder

postorder(mynode *root)
{
  if(root)
  {
    postorder(root->left);
    postorder(root->right);
    printf("Value : [%d]", root->value);
  }
}





Inorder

inorder(mynode *root)
{
  if(root)
  {
    inorder(root->left);
    printf("Value : [%d]", root->value);
    inorder(root->right);
  }
}




Time complexity of traversals is O(n).

Question 27

Write a C program to create a copy of a tree
 


Here is a C program which does that...


mynode *copy(mynode *root)
{
  mynode *temp;
  
  if(root==NULL)return(NULL);
   
  temp = (mynode *) malloc(sizeof(mynode));
  temp->value = root->value;

  temp->left  = copy(root->left);
  temp->right = copy(root->right);

  return(temp);
}







Test Your Skills Now!
Take a Quiz now
Reviewer Name