Need help with this. Please give short explanation. a. What are the ancestors of
ID: 3569887 • Letter: N
Question
Need help with this. Please give short explanation.
a. What are the ancestors of node J?
b. What are the descendants of node T?
c. What are the descendants of node B?
d. What is the order in which the nodes are visited by a preorder traversal?
e. What is the order in which the nodes are visited by a postorder traversal?
Need help with this. Please give short explanation. a. What are the ancestors of node J? b. What are the descendants of node T? c. What are the descendants of node B? d. What is the order in which the nodes are visited by a preorder traversal? e. What is the order in which the nodes are visited by a postorder traversal?Explanation / Answer
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
typedef struct BST {
int data;
struct BST *lchild, *rchild;
} node;
void insert(node *, node *);
void inorder(node *);
void preorder(node *);
void postorder(node *);
node *search(node *, int, node **);
void main() {
int choice;
char ans = 'N';
int key;
node *new_node, *root, *tmp, *parent;
node *get_node();
root = NULL;
clrscr();
printf(" Program For Binary Search Tree ");
do {
printf(" 1.Create");
printf(" 2.Search");
printf(" 3.Recursive Traversals");
printf(" 4.Exit");
printf(" Enter your choice :");
scanf("%d", &choice);
switch (choice) {
case 1:
do {
new_node = get_node();
printf(" Enter The Element ");
scanf("%d", &new_node->data);
if (root == NULL) /* Tree is not Created */
root = new_node;
else
insert(root, new_node);
printf(" Want To enter More Elements?(y/n)");
ans = getch();
} while (ans == 'y');
break;
case 2:
printf(" Enter Element to be searched :");
scanf("%d", &key);
tmp = search(root, key, &parent);
printf(" Parent of node %d is %d", tmp->data, parent->data);
break;
case 3:
if (root == NULL)
printf("Tree Is Not Created");
else {
printf(" The Inorder display : ");
inorder(root);
printf(" The Preorder display : ");
preorder(root);
printf(" The Postorder display : ");
postorder(root);
}
break;
}
} while (choice != 4);
}
/*
Get new Node
*/
node *get_node() {
node *temp;
temp = (node *) malloc(sizeof(node));
temp->lchild = NULL;
temp->rchild = NULL;
return temp;
}
/*
This function is for creating a binary search tree
*/
void insert(node *root, node *new_node) {
if (new_node->data < root->data) {
if (root->lchild == NULL)
root->lchild = new_node;
else
insert(root->lchild, new_node);
}
if (new_node->data > root->data) {
if (root->rchild == NULL)
root->rchild = new_node;
else
insert(root->rchild, new_node);
}
}
/*
This function is for searching the node from
binary Search Tree
*/
node *search(node *root, int key, node **parent) {
node *temp;
temp = root;
while (temp != NULL) {
if (temp->data == key) {
printf(" The %d Element is Present", temp->data);
return temp;
}
*parent = temp;
if (temp->data > key)
temp = temp->lchild;
else
temp = temp->rchild;
}
return NULL;
}
/*
This function displays the tree in inorder fashion
*/
void inorder(node *temp) {
if (temp != NULL) {
inorder(temp->lchild);
printf("%d", temp->data);
inorder(temp->rchild);
}
}
/*
This function displays the tree in preorder fashion
*/
void preorder(node *temp) {
if (temp != NULL) {
printf("%d", temp->data);
preorder(temp->lchild);
preorder(temp->rchild);
}
}
/*
This function displays the tree in postorder fashion
*/
void postorder(node *temp) {
if (temp != NULL) {
postorder(temp->lchild);
postorder(temp->rchild);
printf("%d", temp->data);
}
}
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
typedef struct BST {
int data;
struct BST *lchild, *rchild;
} node;
void insert(node *, node *);
void inorder(node *);
void preorder(node *);
void postorder(node *);
node *search(node *, int, node **);
void main() {
int choice;
char ans = 'N';
int key;
node *new_node, *root, *tmp, *parent;
node *get_node();
root = NULL;
clrscr();
printf(" Program For Binary Search Tree ");
do {
printf(" 1.Create");
printf(" 2.Search");
printf(" 3.Recursive Traversals");
printf(" 4.Exit");
printf(" Enter your choice :");
scanf("%d", &choice);
switch (choice) {
case 1:
do {
new_node = get_node();
printf(" Enter The Element ");
scanf("%d", &new_node->data);
if (root == NULL) /* Tree is not Created */
root = new_node;
else
insert(root, new_node);
printf(" Want To enter More Elements?(y/n)");
ans = getch();
} while (ans == 'y');
break;
case 2:
printf(" Enter Element to be searched :");
scanf("%d", &key);
tmp = search(root, key, &parent);
printf(" Parent of node %d is %d", tmp->data, parent->data);
break;
case 3:
if (root == NULL)
printf("Tree Is Not Created");
else {
printf(" The Inorder display : ");
inorder(root);
printf(" The Preorder display : ");
preorder(root);
printf(" The Postorder display : ");
postorder(root);
}
break;
}
} while (choice != 4);
}
/*
Get new Node
*/
node *get_node() {
node *temp;
temp = (node *) malloc(sizeof(node));
temp->lchild = NULL;
temp->rchild = NULL;
return temp;
}
/*
This function is for creating a binary search tree
*/
void insert(node *root, node *new_node) {
if (new_node->data < root->data) {
if (root->lchild == NULL)
root->lchild = new_node;
else
insert(root->lchild, new_node);
}
if (new_node->data > root->data) {
if (root->rchild == NULL)
root->rchild = new_node;
else
insert(root->rchild, new_node);
}
}
/*
This function is for searching the node from
binary Search Tree
*/
node *search(node *root, int key, node **parent) {
node *temp;
temp = root;
while (temp != NULL) {
if (temp->data == key) {
printf(" The %d Element is Present", temp->data);
return temp;
}
*parent = temp;
if (temp->data > key)
temp = temp->lchild;
else
temp = temp->rchild;
}
return NULL;
}
/*
This function displays the tree in inorder fashion
*/
void inorder(node *temp) {
if (temp != NULL) {
inorder(temp->lchild);
printf("%d", temp->data);
inorder(temp->rchild);
}
}
/*
This function displays the tree in preorder fashion
*/
void preorder(node *temp) {
if (temp != NULL) {
printf("%d", temp->data);
preorder(temp->lchild);
preorder(temp->rchild);
}
}
/*
This function displays the tree in postorder fashion
*/
void postorder(node *temp) {
if (temp != NULL) {
postorder(temp->lchild);
postorder(temp->rchild);
printf("%d", temp->data);
}
}