Solution:

Number Of Nodes:

1. /* 2. * C Program to Find the Number of Nodes in a Binary Tree 3. */ 4. #include <stdio.h> 5. #include <stdlib.h> 6. 7. /* 8. * Structure of node 9. */ 10. struct btnode 11. { 12. int value; 13. struct btnode *l; 14. struct btnode *r; 15. }; 16. 17. void createbinary(); 18. void preorder(node *); 19. int count(node*); 20. node* add(int); 21. 22. typedef struct btnode node; 23. node *ptr, *root = NULL; 24. 25. int main() 26. { 27. int c; 28. 29. createbinary(); 30. preorder(root); 31. c = count(root); 32. printf("\nNumber of nodes in binary tree are:%d\n", c); 33. } 34. /* 35. * constructing the following binary tree 36. * 50 37. * / \ 38. * 20 30 39. * / \ 40. * 70 80 41. * / \ \ 42. *10 40 60 43. */ 44. void createbinary() 45. { 46. root = add(50); 47. root->l = add(20); 48. root->r = add(30); 49. root->l->l = add(70); 50. root->l->r = add(80); 51. root->l->l->l = add(10); 52. root->l->l->r = add(40); 53. root->l->r->r = add(60); 54. } 55. 56. /* 57. * Add the node to binary tree 58. */ 59. node* add(int val) 60. { 61. ptr = (node*)malloc(sizeof(node)); 62. if (ptr == NULL) 63. { 64. printf("Memory was not allocated"); 65. return; 66. } 67. ptr->value = val; 68. ptr->l = NULL; 69. ptr->r = NULL; 70. return ptr; 71. } 72. 73. /* 74. * counting the number of nodes in a tree 75. */ 76. int count(node *n) 77. { 78. int c = 1; 79. 80. if (n == NULL) 81. return 0; 82. else 83. { 84. c += count(n->l); 85. c += count(n->r); 86. return c; 87. } 88. } 89. 90. /* 91. * Displaying the nodes of tree in preorder 92. */ 93. void preorder(node *t) 94. { 95. if (t != NULL) 96. { 97. printf("%d->", t->value); 98. preorder(t->l); 99. preorder(t->r); 100. } 101. }

No. Of Leaf Nodes:

#include <stdio.h>
#include <stdlib.h> /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node
{
int data; struct node* left; struct node* right;
};

/* Function to get the count of leaf nodes in a binary tree*/ unsigned int getLeafCount(struct node* node)
{
if(node == NULL) return 0; if(node->left == NULL && node->right==NULL) return 1; else return getLeafCount(node->left)+ getLeafCount(node->right);
}

/* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data)
{
struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node);
}

/*Driver program to test above functions*/ int main()
{
/*create a tree*/ struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); /*get leaf count of the above created tree*/ printf("Leaf count of the tree is %d", getLeafCount(root)); getchar(); return 0;
}

Depth Of The Tree:

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

/* A binary tree node has data, pointer to left child and a pointer to right child */ struct node
{
int data; struct node* left; struct node* right;
};

/* Compute the "maxDepth" of a tree -- the number of nodes along the longest path from the root node down to the farthest leaf node.*/ int maxDepth(struct node* node)
{
if (node==NULL) return 0; else { /* compute the depth of each subtree */ int lDepth = maxDepth(node->left); int rDepth = maxDepth(node->right); /* use the larger one */ if (lDepth > rDepth) return(lDepth+1); else return(rDepth+1); }
}

/* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data)
{
struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node);
}

int main()
{
struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); printf("Hight of tree is %d", maxDepth(root)); getchar(); return 0;
}

Number of internal Nodes = no of nodes- no of leaf nodes

No. of internal nodes =
1. /*
2. * C Program to Find the Number of Nodes in a Binary Tree
3. */
4. #include <stdio.h>
5. #include <stdlib.h>
6.
7. /*
8. * Structure of node
9. */
10. struct btnode
11. {
12. int value;
13. struct btnode *l;
14. struct btnode *r;
15. };
16.
17. void createbinary();
18. void preorder(node *);
19. int count(node*);
20. node* add(int);
21.
22. typedef struct btnode node;
23. node *ptr, *root = NULL; unsigned int getLeafCount(struct node* node)
{
if(node == NULL) return 0; if(node->left == NULL && node->right==NULL) return 1; else return getLeafCount(node->left)+ getLeafCount(node->right);
}

25. int main()
26. {
27. int c;
28.
29. createbinary();
30. preorder(root);
31. c = count(root); int g = getLeafCount(root); int internal = c- g;
32. printf("\nNumber of internal nodes in binary tree are:%d\n", internal);
33. }
34. /*
35. * constructing the following binary tree
36. * 50
37. * / \
38. * 20 30
39. * / \
40. * 70 80
41. * / \ \
42. *10 40 60
43. */
44. void createbinary()
45. {
46. root = add(50);
47. root->l = add(20);
48. root->r = add(30);
49. root->l->l = add(70);
50. root->l->r = add(80);
51. root->l->l->l = add(10);
52. root->l->l->r = add(40);
53. root->l->r->r = add(60);
54. }
55.
56. /*
57. * Add the node to binary tree
58. */
59. node* add(int val)
60. {
61. ptr = (node*)malloc(sizeof(node));
62. if (ptr == NULL)
63. {
64. printf("Memory was not allocated");
65. return;
66. }
67. ptr->value = val;
68. ptr->l = NULL;
69. ptr->r = NULL;
70. return ptr;
71. }
72.
73. /*
74. * counting the number of nodes in a tree
75. */
76. int count(node *n)
77. {
78. int c = 1;
79.
80. if (n == NULL)
81. return 0;
82. else
83. {
84. c += count(n->l);
85. c += count(n->r);
86. return c;
87. }
88. }
89.
90. /*
91. * Displaying the nodes of tree in preorder
92. */
93. void preorder(node *t)
94. {
95. if (t != NULL)
96. {
97. printf("%d->", t->value);
98. preorder(t->l);
99. preorder(t->r);
100. }
101. }

For 1 through 6, the most important concept is of the Big-Oh notation f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

So, for the questions

Since We have to prove that f(n) < cg(n), only the terms with the HIGHEST COEFFECIENT matters, or the term which has the MAXIMUM VALUE

1. The maximum of those two will be used for the Big-Oh definition. This is just the definition of Big-Oh.
Since O(f(n)+g(n)) is effectively the O() of whichever one if bigger, that is exactly what’s written on the Left hand side.

2. Similarly, since n^5 is the fastest growing term, this is the only term which will matter in finding the Big-Oh, since big Oh needs to prove that f(n) can be SUPPRESSED by g(n) in every case

3. 2^n+1 can be written as 2*2^n, which is of the form c*2^n. Therefore, 2^n+1 = O(2^n)

4. Sum of i^2, i=0 to n is equal to n*(n+1)*(2n+1)/6 which in turn has n^3 as the highest degree term, i.e. the fastest growing term. Hence, O(n^3) is the answer to this.

5. Use this as a practice exercise for yourself. It’s really easy and all you have to do is arrange them in their order of growth, i.e. loglogn grows slower than log^2 (n) , etc
2^100, loglogn, log^2n, sqrt(logn), 1/n, n ^0.01 ,[3sqrt(n), Sqrt(n)], 5n, [nlog4n,6nlogn], 2nlog^2n,4*n^3/2, n^2logn
2^logn, 4^logn, 2^n, [4^n, 2^2^n]

6. Wrong Question. T(n) will be equal to 2^(n+1) – 3

7. Root- if(p->parent == NULL)

Parent- if(p->leftChild !=NULL || p->rightChild !=NULL)

Left Child if(p->parent->left == p)

Right Child id(p->parent->right == p)

isInternal if(p->leftChild !=NULL &&p->rightChild !=NULL && p->parent!=NULL)