Q1) The key of each node in a binary-search-tree is a short character
string.  a) Show how such a tree would look like after the following
words were inserted (in the order indicated): monkey canary donkey
deer zebra yak walrus vulture penguin quail b) How the tree would look
like if the same word were inserted in the order quail walrus donkey
deer monkey vulture yak penguin zebra canary

Q2) One Hundred elements are chosen at random and inserted into a
sorted linked list and a binary search tree. Describe the efficiency
of searching for an element in each structure, in term of Big-O
notation. What if elements are inserted in order, from smallest to
largest?

Q3) Write a function Predecessor(X) which returns a pointer to the
predecessor of the node X in BST.  Q4) Write a boolean function IsBST
that determine whether a given binary tree is BST.

Q5) write a function LeafCount that returns the number of leaf noads
in the BST.

Q6) Write a function SingleParentCount that returns the number of
nodes in the BSt that have only one child.

Q7) Write a boolean function SimilarTrees that receives pointers to
two binary tree and determine whether the shapes of the tree are the
same. (The Nodes do not have to contain the same value, but each node
have the same number of childrens).  Note: To create two binary search
trees, generate 200 random numbers, Use first 100 numbers to create
the first BST and use next to create the second BST.      

Q8) #include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Linked list Node Structure */
struct lnode {
 int val;
 struct lnode *next;
};

/* Binary Search Tree Node Structure */
struct bst {
 int num;
 struct bst *left;
 struct bst *right;
};


struct lnode* makeList();    /* Creates a  singly linked list which will be
your input */
struct bst* makeBST(struct lnode*); /* Code this function */
void preorder(struct bst*);         /* Code this function */

int main(void) {
         int num;

        struct lnode *list;
        struct bst *tree;
        tree=NULL;
        list = makeList();

        tree = makeBST(list);
        inorder(tree);
}

/* This program return a link list containing 100 integers in sorted order */
struct lnode* makeList() {
        int i=0,data;
        struct lnode* list=NULL;
        struct lnode *p;
        struct lnode *q;
        for(i=0;i<100;i++)
        {
                data = rand()%1000;

                p = (struct lnode *)malloc(sizeof(struct lnode));
                p->val = data;

                if(list == NULL || list->val > data) {

                        p->next = list;
                        list=p;

                } else
                {
                        q = list;
                        while(q->next != NULL && q->next->val < data) {
                                q = q->next;
                        }
                        p->next = q->next;
                        q->next = p;

                }
        }
        return list;
                                       


}

/* Given a singly linked list you have to create a binary search tree. You
 * have to use
following steps.
1. Determine the middle element of linked list.
2. Make it the parent node whose left child will be
        a) left child will be the middle node of the left half and
        b) right child will be middle node of the right half
3. The subtrees rooted at left child and the right child will be similarly
created recursively.
4. Do not forget to handle boundary cases.
*/
struct bst* makeBST(struct lnode* list){
/* Have to Write your function here */
}

/*
Prints the inorder traversal of the resultant binary search tree.
*/

void inorder(struct bst* tree){
/* Have to Write your code here */
}

void print_list(struct lnode *list) {
 struct lnode *p;
 p=list;
 while(p){
   printf("%d\n", p->val);
   p=p->next;
   }
}


Q9) #include <stdio.h>
#include <stdlib.h>


struct node
{
  int data;
  struct node *left, *right;
};

/* You have to implement the below given function that checks whether
 * a given BST tree is symmetric.
A BST is symmetric if left subtree and the right subtree have the same
structure.

*/
int  is_symmetric(struct node *k);

void inorder (struct node *p);
main ()
{
  struct node *root = NULL, *new = NULL, *temp1 = NULL, *temp2 = NULL;
  int num = 0, t, i = 0;
  srand ((unsigned int) time ((time_t *) NULL));
  for (i = 0; i < 100; i++)
    {
      t = rand ();
      num = t;
      new = malloc (sizeof (struct node));
      new->left = new->right = NULL;
      new->data = num;

      if (root == NULL)
        root = new;
      else
        {
          temp1 = root;
          while (temp1 != NULL)
            {
              temp2 = temp1;

              if (new->data > temp1->data)
                temp1 = temp1->right;
              else
                temp1 = temp1->left;

            }

          if (new->data > temp2->data)
            temp2->right = new;
          else
            temp2->left = new;
        }
    }
   is_symmetric(root);
  inorder (root);
}


int  is_symmetric(struct node *k)
{

/* Write your code Here   */
}

void
inorder (struct node *p)
{
  if (p != NULL)
    {
      inorder (p->left);
      printf ("%d ", p->data);
      inorder (p->right);
    }
}