Find out in given two trees T and S. Tree S is subset of Tree T.

Ex:         S                   T
            10                 40
           /  \                 /      \
         8    12          10       45
          \                 /  \        /    \
          9                8   12  43  50
                              \
                               9
                       
    Tree S is subset of Tree T.

1:  #include <stdio.h>  
2:  #include <stdlib.h>  
3:  #define MAIN_TREE 1  
4:  #define SUB_TREE 2  
5:  typedef struct my_tree  
6:  {  
7:    struct my_tree *left;  
8:    struct my_tree *right;  
9:    int tdata;  
10:  }my_tree_t;  
11:  my_tree_t *T = NULL, *S = NULL;  
12:  void preorder(my_tree_t *node)  
13:  {  
14:    if ( NULL == node)  
15:      return;  
16:    printf("%d\t",node->tdata);  
17:    preorder(node->left);  
18:    preorder(node->right);  
19:  }  
20:  my_tree_t *get_newnode(int data)  
21:  {  
22:    my_tree_t *newnode = (my_tree_t*)malloc(sizeof(my_tree_t));  
23:    newnode->tdata = data;  
24:    newnode->left = NULL;  
25:    newnode->right = NULL;  
26:    return newnode;  
27:  }  
28:  my_tree_t *add_node_to_tree(my_tree_t *node, int data,int flag)  
29:  {  
30:    if( NULL == node)  
31:    {  
32:      node = get_newnode(data);  
33:      if ( flag == MAIN_TREE && NULL == T)  
34:        T = node;  
35:      if ( flag == SUB_TREE && NULL == S)  
36:        S = node;  
37:    }  
38:    if ( node->tdata < data) {  
39:      node->right = add_node_to_tree(node->right,data,flag);  
40:    } else if (node->tdata > data) {  
41:      node->left = add_node_to_tree(node->left,data,flag);  
42:    }  
43:    return node;  
44:  }  
45:  my_tree_t *find_sub_node_in_main_tree(my_tree_t *node,int data)  
46:  {  
47:    my_tree_t *temp = NULL;  
48:    if ( NULL == node )  
49:      return NULL;  
50:    if ( node->tdata == data )  
51:      return node;  
52:    temp = find_sub_node_in_main_tree(node->left,data);  
53:    if ( NULL != temp && temp->tdata == data )  
54:      temp = find_sub_node_in_main_tree(temp,data);  
55:    else  
56:      find_sub_node_in_main_tree(node->right,data);  
57:  }  
58:  int check_for_complete_subtree(my_tree_t *T, my_tree_t *S)  
59:  {  
60:    if ( NULL == S )  
61:    {  
62:      return 0;  
63:    }  
64:    if ( NULL == T)  
65:    {  
66:      return 1;  
67:    }  
68:    if( T->tdata != S->tdata)  
69:    {  
70:      return 1;  
71:    }  
72:    check_for_complete_subtree(T->left,S->left);  
73:    check_for_complete_subtree(T->right,S->right);  
74:  }  
75:  int check_for_sub_tree(my_tree_t *T, my_tree_t *S)  
76:  {  
77:    my_tree_t *node = NULL;  
78:    node = find_sub_node_in_main_tree(T,S->tdata);  
79:    if ( NULL == node)  
80:    {  
81:      printf("Head of subtree is not present in main Tree\n");  
82:      return 1;  
83:    }  
84:    printf("Head node of sub tree is found in main tree %d\n",node->tdata);  
85:    if ( 0 == check_for_complete_subtree(node,S))  
86:      return 0;  
87:    else  
88:      return 1;  
89:  }  
90:  main()  
91:  {  
92:    int main_tree[]= {40,45,10,43,8,50,55,12,9,0};  
93:    int sub_tree[] = {10,8,12,9,0};  
94:    int choice, i=0;  
95:    printf("1.Add node into main Tree\n");  
96:    for(i = 0; main_tree[i] != 0; i++)  
97:    {  
98:      add_node_to_tree(T,main_tree[i],MAIN_TREE);  
99:    }  
100:    printf("Done.\n");  
101:    printf("1.Add node into main Tree\n");  
102:    for(i = 0; sub_tree[i] != 0; i++)  
103:    {  
104:      add_node_to_tree(S,sub_tree[i],SUB_TREE);  
105:    }  
106:    printf("Display main tree\n");  
107:    preorder(T);  
108:    printf("Done.\n");  
109:    printf("Display Sub Tree\n");  
110:    preorder(S);  
111:    printf("Done.\n");  
112:    if ( 0 == check_for_sub_tree(T,S) )  
113:      printf("Tree S is Subset of Tree T\n");  
114:    else  
115:      printf("Tree S is not a subset of Tree T\n");  
116:  }