socket tutorials seen feel good:
http://www.binarytides.com/category/programming/sockets/c-sockets/
http://www.binarytides.com/socket-programming-c-linux-tutorial/
http://www.scs.stanford.edu/07wi-cs244b/refs/net2.pdf
https://www.cs.utah.edu/~swalton/listings/sockets/programs/
BST dumps:
level of given node:
Steps:
Start at the Root with level=0
If ptr == root pointer
return level
Else
Call the function recursively for left subtree and right subtree
01 #include<stdio.h>
02
03 /* A tree node structure */
04 struct node
05 {
06 int data;
07 struct node *left;
08 struct node *right;
09 };
10
11 int getLevel(struct node* root, int n, int level)
12 {
13 if(root == NULL)
14 return 0;
15
16 if(root->data == n)
17 return level;
18
19 return getLevel(root->left, n, level+1) |
20 getLevel(root->right, n, level+1);
21 }
22
23 /* Utility function to create a new Binary Tree node */
24 struct node* newNode(int data)
25 {
26 struct node *temp = new struct node;
27 temp->data = data;
28 temp->left = NULL;
29 temp->right = NULL;
30
31 return temp;
32 }
33
34 /* Driver function to test above functions */
35 int main()
36 {
37 struct node *root = new struct node;
38 int x;
39
40 /* Constructing tree given in the above figure */
41 root = newNode(0);
42 root->left = newNode(1);
43 root->right = newNode(4);
44 root->left->left = newNode(2);
45 root->left->right = newNode(3);
46 root->right->left = newNode(5);
47 root->right->right = newNode(6);
48
49
50 int level = getLevel(root, 5, 1);
51 printf("%d",level);
52
53 return 0;
54 }
Check if a binary tree is subtree of another tree
Solution:
Traverse T1 in pre-order fashion. For each node, check if the subtree rooted at this node is identical (exactly same) as T2.
01 struct node
02 {
03 int data;
04 struct node* left;
05 struct node* right;
06 };
07 bool identical(struct node * root1, struct node *root2)
08 {
09 if(root1 == NULL && root2 == NULL)
10 return true;
11
12 if(root1 == NULL || root2 == NULL)
13 return false;
14
15 return (root1->data == root2->data &&
16 identical(root1->left, root2->left) &&
17 identical(root1->right, root2->right) );
18 }
19
20 bool checkSubtree(struct node *T1, struct node *T2)
21 {
22 if (T2 == NULL)
23 return true;
24
25 if (T1 == NULL)
26 return false;
27
28 if (identical(T1, T2))
29 return true;
30
31 return checkSubtree(T1->left, T2) ||
32 checkSubtree(T1->right, T2);
33 }
Find largest BST in a binary tree
A tree is a BST if:
1. Both left and right subtrees of a node are BSTs.
2. The node’s value is greater than its left subtree’s maximum value.
3. The node’s value is less than its right subtree’s minimum value.
Top-Down approach : Starting from the root, we process in the order of current node, left child, then right child. For each node, call isBST() to check if the current subtree is a BST. If it is, then we have found the largest BST subtree. If it is not, then check its left and right child. If only one of the subtrees is BST, then we can return that subtree. However, if both left and right subtrees are BSTs, then we have to compare which subtree is larger (has more descendant nodes), then return the larger one.
Bottom-Up Approach:In Bottom up approach, we need to pass some information up the tree. Obviously, we need to pass minimum and maximum values of the subtree as we traverse up the tree, so the above subtrees could be verified for BST’s properties.
Bottom-Up approach,as compared to the top-down approach, saves us from recalculating over and over again. The total number of nodes for a subtree is simply the total number of nodes of its left and right subtrees plus one.
The run-time complexity for the bottom-up approach is O(n).Even though a node’s left subtree is not a BST, you must still continue traverse its right subtree as the largest BST subtree might be contained in its right subtree.
01 struct node
02 {
03 int data;
04 struct node* left;
05 struct node* right;
06 };
07 int largestBST(struct node* root, int& min, int& max, int& size,struct node* & bstRoot);
08
09 struct node* findLargestBSTSubtree(struct node *root) {
10 struct node *bstRoot = NULL;
11 int min, max;
12 int maxNodes = INT_MIN;
13 largestBST(root, min, max, maxNodes,bstRoot);
14 return bstRoot;
15 }
16
17 int largestBST(struct node* root, int& min, int& max, int& size,struct node* & bstRoot)
18 {
19 if(root == NULL)
20 return 0;
21
22 int leftMin = INT_MIN, rightMin = INT_MIN;
23 int leftMax = INT_MAX, rightMax = INT_MAX;
24 int x,y;
25
26 x = largestBST(root->left, leftMin, leftMax, size,bstRoot);
27 y = largestBST(root->right, rightMin, rightMax, size,bstRoot);
28
29 if(x==-1 || y ==-1)
30 return -1;
31 if(x==0)
32 {
33 leftMax = root->data;
34 leftMin = root->data;
35 }
36 if(y==0)
37 {
38 rightMin = root->data;
39 rightMax = root->data;
40 }
41
42 if(root->data < leftMax || root->data > rightMin)
43 return -1;
44
45 min = leftMin;
46 max = rightMax;
47
48
49 if(x+y+1 > size){
50 size = x+y+1;
51 bstRoot = root;
52 }
53 return x+y+1;
54 }
Print BST elements in range K1 and K2
Problem: Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a element of given BST.
Steps:
1) If value of root node is greater than k1, then recursively call in left subtree.
2) If value of root node is smaller than k2, then recursively call in right subtree.
3) If value of root node is in range, then print the root’s value.
Implementation:
01 /* The function assumes that k1 < k2 */
02 void printBST(Struct node* node, int k1, int k2)
03 {
04 if(node==NULL) return;
05 if(node->data<=k2 && node->data>=k1)
06 {
07 printf("%d", node->data);
08 }
09 else if(node->data < k1) printBST(node->left, k1, k2);
10 else if(node->data > k2) printBST(node->right, k1, k2);
11 }
*
Returns true if a binary tree is a binary search tree.
*/
int isBST(struct node* node) {
if (node==NULL) return(true);
// false if the min of the left is > than us
if (node->left!=NULL && minValue(node->left) > node->data)
return(false);
// false if the max of the right is <= than us
if (node->right!=NULL && maxValue(node->right) <= node->data)
return(false);
// false if, recursively, the left or right is not a BST
if (!isBST(node->left) || !isBST(node->right))
return(false);
// passing all that, it's a BST
return(true);
}
/*
Returns true if the given tree is a binary search tree
(efficient version).
*/
int isBST2(struct node* node) {
return(isBSTUtil(node, INT_MIN, INT_MAX));
}
/*
Returns true if the given tree is a BST and its
values are >= min and <= max.
*/
int isBSTUtil(struct node* node, int min, int max) {
if (node==NULL) return(true);
// false if this node violates the min/max constraint
if (node->data<min || node->data>max) return(false);
// otherwise check the subtrees recursively,
// tightening the min or max constraint
return
isBSTUtil(node->left, min, node->data) &&
isBSTUtil(node->right, node->data+1, max)
);
}
iteratuve inorder /preorder/postorder
Here is a complete C program which prints a BST using both recursion and iteration. The best way to understand these algorithms is to get a pen and a paper and trace out the traversals (with the stack or the queue) alongside. Dont even try to memorize these algorithms!
tree traversals pre order, post prder, in order
tree_traversals
001 #include <stdio.h>
002
003 typedef struct node
004 {
005 int value;
006 struct node *right;
007 struct node *left;
008 }mynode;
009
010 mynode *root;
011
012 add_node(int value);
013 void postorder(mynode *root);
014 void inorder(mynode *root);
015 void preorder(mynode *root);
016
017 void iterativePreorder(mynode *root);
018 void iterativeInorder (mynode *root);
019 void iterativePostorder(mynode *root);
020
021
022 int main(int argc, char* argv[])
023 {
024 root = NULL;
025
026 add_node(5);
027 add_node(1);
028 add_node(-20);
029 add_node(100);
030 add_node(23);
031 add_node(67);
032 add_node(13);
033
034 printf("\nPreorder (R) : ");
035 preorder(root);
036 printf("\nPreorder (I) : ");
037 iterativePreorder(root);
038
039 printf("\n\nPostorder (R) : ");
040 postorder(root);
041 printf("\nPostorder (R) : ");
042 iterativePostorder(root);
043
044
045 printf("\n\nInorder (R) : ");
046 inorder(root);
047 printf("\nInorder (I) : ");
048 iterativeInorder(root);
049
050 }
051
052 // Function to add a new node to the BST
053 add_node(int value)
054 {
055 mynode *prev, *cur, *temp;
056
057 temp = (mynode *) malloc(sizeof(mynode));
058 temp->value = value;
059 temp->right = NULL;
060 temp->left = NULL;
061
062 if(root==NULL)
063 {
064 printf("\nCreating the root..\n");
065 root = temp;
066 return;
067 }
068
069 prev=NULL;
070 cur=root;
071
072 while(cur!=NULL)
073 {
074 prev=cur;
075 cur=(value<cur->value)?cur->left:cur->right;
076 }
077
078 if(value < prev->value)
079 prev->left=temp;
080 else
081 prev->right=temp;
082 }
083
084
085 // Recursive Preorder
086 void preorder(mynode *root)
087 {
088 if(root)
089 {
090 printf("[%d] ", root->value);
091 preorder(root->left);
092 preorder(root->right);
093 }
094 }
095
096 // Iterative Preorder
097 void iterativePreorder(mynode *root)
098 {
099 mynode *save[100];
100 int top = 0;
101
102 if (root == NULL)
103 {
104 return;
105 }
106
107 save[top++] = root;
108 while (top != 0)
109 {
110 root = save[--top];
111
112 printf("[%d] ", root->value);
113
114 if (root->right != NULL)
115 save[top++] = root->right;
116 if (root->left != NULL)
117 save[top++] = root->left;
118 }
119 }
120
121 // Recursive Postorder
122 void postorder(mynode *root)
123 {
124 if(root)
125 {
126 postorder(root->left);
127 postorder(root->right);
128 printf("[%d] ", root->value);
129 }
130 }
131
132 // Iterative Postorder
133 void iterativePostorder(mynode *root)
134 {
135 struct
136 {
137 mynode *node;
138 unsigned vleft :1; // Visited left?
139 unsigned vright :1; // Visited right?
140 }save[100];
141
142 int top = 0;
143
144 save[top++].node = root;
145
146 while ( top != 0 )
147 {
148 /* Move to the left subtree if present and not visited */
149 if(root->left != NULL && !save[top].vleft)
150 {
151 save[top].vleft = 1;
152 save[top++].node = root;
153 root = root->left;
154 continue;
155 }
156
157 /* Move to the right subtree if present and not visited */
158 if(root->right != NULL && !save[top].vright )
159 {
160 save[top].vright = 1;
161 save[top++].node = root;
162 root = root->right;
163 continue;
164 }
165
166 printf("[%d] ", root->value);
167
168 /* Clean up the stack */
169 save[top].vleft = 0;
170 save[top].vright = 0;
171
172 /* Move up */
173 root = save[--top].node;
174 }
175 }
176
177
178 // Recursive Inorder
179 void inorder(mynode *root)
180 {
181 if(root)
182 {
183 inorder(root->left);
184 printf("[%d] ", root->value);
185 inorder(root->right);
186 }
187 }
188
189
190 // Iterative Inorder..
191 void iterativeInorder (mynode *root)
192 {
193 mynode *save[100];
194 int top = 0;
195
196 while(root != NULL)
197 {
198 while (root != NULL)
199 {
200 if (root->right != NULL)
201 {
202 save[top++] = root->right;
203 }
204 save[top++] = root;
205 root = root->left;
206 }
207
208 root = save[--top];
209 while(top != 0 && root->right == NULL)
210 {
211 printf("[%d] ", root->value);
212 root = save[--top];
213 }
214
215 printf("[%d] ", root->value);
216 root = (top != 0) ? save[--top] : (mynode *) NULL;
217 }
218 }
And here is the output…
Creating the root..
Preorder (R) : [10] [5] [4] [1] [8] [30] [40]
Preorder (I) : [10] [5] [4] [1] [8] [30] [40]
Postorder (R) : [1] [4] [8] [5] [40] [30] [10]
Postorder (R) : [1] [4] [8] [5] [40] [30] [10]
Inorder (R) : [1] [4] [5] [8] [10] [30] [40]
Inorder (I) : [1] [4] [5] [8] [10] [30] [40
Print Level Order Traversal of a tree
1 2 3 4 5 6
Approach:
Starting from the root, first the node is visited and printed then it’s child nodes are put in a queue.
01 struct node
02 {
03 int value;
04 struct node* left;
05 struct node* right;
06 };
07 void levelOrderTraversal(struct node *root)
08 {
09 struct node *queue[100] = {(struct node *)0};
10 int size = 0;
11 int queue_pointer = 0;
12 struct node *temp = root;
13 while(temp)
14 {
15 printf("%d", temp->value);
16 if(temp->left)
17 {
18 queue[size++] = temp->left;
19 }
20
21 if(temp->right)
22 {
23 queue[size++] = temp->right;
24 }
25 temp = queue[queue_pointer++];
26 }
27 }
Time Complexity:
As we are visiting each node once.So the time complexity would be O(n) where n is the number of nodes in the tree.
source:
http://www.crazyforcode.com/tree/
IP:
http://packetlife.net/library/cheat-sheets/
IP packet fragmentation
http://mars.netanya.ac.il/~unesco/cdrom/booklet/HTML/NETWORKING/node020.html
http://www.binarytides.com/category/programming/sockets/c-sockets/
http://www.binarytides.com/socket-programming-c-linux-tutorial/
http://www.scs.stanford.edu/07wi-cs244b/refs/net2.pdf
https://www.cs.utah.edu/~swalton/listings/sockets/programs/
BST dumps:
level of given node:
Steps:
Start at the Root with level=0
If ptr == root pointer
return level
Else
Call the function recursively for left subtree and right subtree
01 #include<stdio.h>
02
03 /* A tree node structure */
04 struct node
05 {
06 int data;
07 struct node *left;
08 struct node *right;
09 };
10
11 int getLevel(struct node* root, int n, int level)
12 {
13 if(root == NULL)
14 return 0;
15
16 if(root->data == n)
17 return level;
18
19 return getLevel(root->left, n, level+1) |
20 getLevel(root->right, n, level+1);
21 }
22
23 /* Utility function to create a new Binary Tree node */
24 struct node* newNode(int data)
25 {
26 struct node *temp = new struct node;
27 temp->data = data;
28 temp->left = NULL;
29 temp->right = NULL;
30
31 return temp;
32 }
33
34 /* Driver function to test above functions */
35 int main()
36 {
37 struct node *root = new struct node;
38 int x;
39
40 /* Constructing tree given in the above figure */
41 root = newNode(0);
42 root->left = newNode(1);
43 root->right = newNode(4);
44 root->left->left = newNode(2);
45 root->left->right = newNode(3);
46 root->right->left = newNode(5);
47 root->right->right = newNode(6);
48
49
50 int level = getLevel(root, 5, 1);
51 printf("%d",level);
52
53 return 0;
54 }
Check if a binary tree is subtree of another tree
Solution:
Traverse T1 in pre-order fashion. For each node, check if the subtree rooted at this node is identical (exactly same) as T2.
01 struct node
02 {
03 int data;
04 struct node* left;
05 struct node* right;
06 };
07 bool identical(struct node * root1, struct node *root2)
08 {
09 if(root1 == NULL && root2 == NULL)
10 return true;
11
12 if(root1 == NULL || root2 == NULL)
13 return false;
14
15 return (root1->data == root2->data &&
16 identical(root1->left, root2->left) &&
17 identical(root1->right, root2->right) );
18 }
19
20 bool checkSubtree(struct node *T1, struct node *T2)
21 {
22 if (T2 == NULL)
23 return true;
24
25 if (T1 == NULL)
26 return false;
27
28 if (identical(T1, T2))
29 return true;
30
31 return checkSubtree(T1->left, T2) ||
32 checkSubtree(T1->right, T2);
33 }
Find largest BST in a binary tree
A tree is a BST if:
1. Both left and right subtrees of a node are BSTs.
2. The node’s value is greater than its left subtree’s maximum value.
3. The node’s value is less than its right subtree’s minimum value.
Top-Down approach : Starting from the root, we process in the order of current node, left child, then right child. For each node, call isBST() to check if the current subtree is a BST. If it is, then we have found the largest BST subtree. If it is not, then check its left and right child. If only one of the subtrees is BST, then we can return that subtree. However, if both left and right subtrees are BSTs, then we have to compare which subtree is larger (has more descendant nodes), then return the larger one.
Bottom-Up Approach:In Bottom up approach, we need to pass some information up the tree. Obviously, we need to pass minimum and maximum values of the subtree as we traverse up the tree, so the above subtrees could be verified for BST’s properties.
Bottom-Up approach,as compared to the top-down approach, saves us from recalculating over and over again. The total number of nodes for a subtree is simply the total number of nodes of its left and right subtrees plus one.
The run-time complexity for the bottom-up approach is O(n).Even though a node’s left subtree is not a BST, you must still continue traverse its right subtree as the largest BST subtree might be contained in its right subtree.
01 struct node
02 {
03 int data;
04 struct node* left;
05 struct node* right;
06 };
07 int largestBST(struct node* root, int& min, int& max, int& size,struct node* & bstRoot);
08
09 struct node* findLargestBSTSubtree(struct node *root) {
10 struct node *bstRoot = NULL;
11 int min, max;
12 int maxNodes = INT_MIN;
13 largestBST(root, min, max, maxNodes,bstRoot);
14 return bstRoot;
15 }
16
17 int largestBST(struct node* root, int& min, int& max, int& size,struct node* & bstRoot)
18 {
19 if(root == NULL)
20 return 0;
21
22 int leftMin = INT_MIN, rightMin = INT_MIN;
23 int leftMax = INT_MAX, rightMax = INT_MAX;
24 int x,y;
25
26 x = largestBST(root->left, leftMin, leftMax, size,bstRoot);
27 y = largestBST(root->right, rightMin, rightMax, size,bstRoot);
28
29 if(x==-1 || y ==-1)
30 return -1;
31 if(x==0)
32 {
33 leftMax = root->data;
34 leftMin = root->data;
35 }
36 if(y==0)
37 {
38 rightMin = root->data;
39 rightMax = root->data;
40 }
41
42 if(root->data < leftMax || root->data > rightMin)
43 return -1;
44
45 min = leftMin;
46 max = rightMax;
47
48
49 if(x+y+1 > size){
50 size = x+y+1;
51 bstRoot = root;
52 }
53 return x+y+1;
54 }
Print BST elements in range K1 and K2
Problem: Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a element of given BST.
Steps:
1) If value of root node is greater than k1, then recursively call in left subtree.
2) If value of root node is smaller than k2, then recursively call in right subtree.
3) If value of root node is in range, then print the root’s value.
Implementation:
01 /* The function assumes that k1 < k2 */
02 void printBST(Struct node* node, int k1, int k2)
03 {
04 if(node==NULL) return;
05 if(node->data<=k2 && node->data>=k1)
06 {
07 printf("%d", node->data);
08 }
09 else if(node->data < k1) printBST(node->left, k1, k2);
10 else if(node->data > k2) printBST(node->right, k1, k2);
11 }
*
Returns true if a binary tree is a binary search tree.
*/
int isBST(struct node* node) {
if (node==NULL) return(true);
// false if the min of the left is > than us
if (node->left!=NULL && minValue(node->left) > node->data)
return(false);
// false if the max of the right is <= than us
if (node->right!=NULL && maxValue(node->right) <= node->data)
return(false);
// false if, recursively, the left or right is not a BST
if (!isBST(node->left) || !isBST(node->right))
return(false);
// passing all that, it's a BST
return(true);
}
/*
Returns true if the given tree is a binary search tree
(efficient version).
*/
int isBST2(struct node* node) {
return(isBSTUtil(node, INT_MIN, INT_MAX));
}
/*
Returns true if the given tree is a BST and its
values are >= min and <= max.
*/
int isBSTUtil(struct node* node, int min, int max) {
if (node==NULL) return(true);
// false if this node violates the min/max constraint
if (node->data<min || node->data>max) return(false);
// otherwise check the subtrees recursively,
// tightening the min or max constraint
return
isBSTUtil(node->left, min, node->data) &&
isBSTUtil(node->right, node->data+1, max)
);
}
iteratuve inorder /preorder/postorder
Here is a complete C program which prints a BST using both recursion and iteration. The best way to understand these algorithms is to get a pen and a paper and trace out the traversals (with the stack or the queue) alongside. Dont even try to memorize these algorithms!
tree traversals pre order, post prder, in order
tree_traversals
001 #include <stdio.h>
002
003 typedef struct node
004 {
005 int value;
006 struct node *right;
007 struct node *left;
008 }mynode;
009
010 mynode *root;
011
012 add_node(int value);
013 void postorder(mynode *root);
014 void inorder(mynode *root);
015 void preorder(mynode *root);
016
017 void iterativePreorder(mynode *root);
018 void iterativeInorder (mynode *root);
019 void iterativePostorder(mynode *root);
020
021
022 int main(int argc, char* argv[])
023 {
024 root = NULL;
025
026 add_node(5);
027 add_node(1);
028 add_node(-20);
029 add_node(100);
030 add_node(23);
031 add_node(67);
032 add_node(13);
033
034 printf("\nPreorder (R) : ");
035 preorder(root);
036 printf("\nPreorder (I) : ");
037 iterativePreorder(root);
038
039 printf("\n\nPostorder (R) : ");
040 postorder(root);
041 printf("\nPostorder (R) : ");
042 iterativePostorder(root);
043
044
045 printf("\n\nInorder (R) : ");
046 inorder(root);
047 printf("\nInorder (I) : ");
048 iterativeInorder(root);
049
050 }
051
052 // Function to add a new node to the BST
053 add_node(int value)
054 {
055 mynode *prev, *cur, *temp;
056
057 temp = (mynode *) malloc(sizeof(mynode));
058 temp->value = value;
059 temp->right = NULL;
060 temp->left = NULL;
061
062 if(root==NULL)
063 {
064 printf("\nCreating the root..\n");
065 root = temp;
066 return;
067 }
068
069 prev=NULL;
070 cur=root;
071
072 while(cur!=NULL)
073 {
074 prev=cur;
075 cur=(value<cur->value)?cur->left:cur->right;
076 }
077
078 if(value < prev->value)
079 prev->left=temp;
080 else
081 prev->right=temp;
082 }
083
084
085 // Recursive Preorder
086 void preorder(mynode *root)
087 {
088 if(root)
089 {
090 printf("[%d] ", root->value);
091 preorder(root->left);
092 preorder(root->right);
093 }
094 }
095
096 // Iterative Preorder
097 void iterativePreorder(mynode *root)
098 {
099 mynode *save[100];
100 int top = 0;
101
102 if (root == NULL)
103 {
104 return;
105 }
106
107 save[top++] = root;
108 while (top != 0)
109 {
110 root = save[--top];
111
112 printf("[%d] ", root->value);
113
114 if (root->right != NULL)
115 save[top++] = root->right;
116 if (root->left != NULL)
117 save[top++] = root->left;
118 }
119 }
120
121 // Recursive Postorder
122 void postorder(mynode *root)
123 {
124 if(root)
125 {
126 postorder(root->left);
127 postorder(root->right);
128 printf("[%d] ", root->value);
129 }
130 }
131
132 // Iterative Postorder
133 void iterativePostorder(mynode *root)
134 {
135 struct
136 {
137 mynode *node;
138 unsigned vleft :1; // Visited left?
139 unsigned vright :1; // Visited right?
140 }save[100];
141
142 int top = 0;
143
144 save[top++].node = root;
145
146 while ( top != 0 )
147 {
148 /* Move to the left subtree if present and not visited */
149 if(root->left != NULL && !save[top].vleft)
150 {
151 save[top].vleft = 1;
152 save[top++].node = root;
153 root = root->left;
154 continue;
155 }
156
157 /* Move to the right subtree if present and not visited */
158 if(root->right != NULL && !save[top].vright )
159 {
160 save[top].vright = 1;
161 save[top++].node = root;
162 root = root->right;
163 continue;
164 }
165
166 printf("[%d] ", root->value);
167
168 /* Clean up the stack */
169 save[top].vleft = 0;
170 save[top].vright = 0;
171
172 /* Move up */
173 root = save[--top].node;
174 }
175 }
176
177
178 // Recursive Inorder
179 void inorder(mynode *root)
180 {
181 if(root)
182 {
183 inorder(root->left);
184 printf("[%d] ", root->value);
185 inorder(root->right);
186 }
187 }
188
189
190 // Iterative Inorder..
191 void iterativeInorder (mynode *root)
192 {
193 mynode *save[100];
194 int top = 0;
195
196 while(root != NULL)
197 {
198 while (root != NULL)
199 {
200 if (root->right != NULL)
201 {
202 save[top++] = root->right;
203 }
204 save[top++] = root;
205 root = root->left;
206 }
207
208 root = save[--top];
209 while(top != 0 && root->right == NULL)
210 {
211 printf("[%d] ", root->value);
212 root = save[--top];
213 }
214
215 printf("[%d] ", root->value);
216 root = (top != 0) ? save[--top] : (mynode *) NULL;
217 }
218 }
And here is the output…
Creating the root..
Preorder (R) : [10] [5] [4] [1] [8] [30] [40]
Preorder (I) : [10] [5] [4] [1] [8] [30] [40]
Postorder (R) : [1] [4] [8] [5] [40] [30] [10]
Postorder (R) : [1] [4] [8] [5] [40] [30] [10]
Inorder (R) : [1] [4] [5] [8] [10] [30] [40]
Inorder (I) : [1] [4] [5] [8] [10] [30] [40
Print Level Order Traversal of a tree
1 2 3 4 5 6
Approach:
Starting from the root, first the node is visited and printed then it’s child nodes are put in a queue.
01 struct node
02 {
03 int value;
04 struct node* left;
05 struct node* right;
06 };
07 void levelOrderTraversal(struct node *root)
08 {
09 struct node *queue[100] = {(struct node *)0};
10 int size = 0;
11 int queue_pointer = 0;
12 struct node *temp = root;
13 while(temp)
14 {
15 printf("%d", temp->value);
16 if(temp->left)
17 {
18 queue[size++] = temp->left;
19 }
20
21 if(temp->right)
22 {
23 queue[size++] = temp->right;
24 }
25 temp = queue[queue_pointer++];
26 }
27 }
Time Complexity:
As we are visiting each node once.So the time complexity would be O(n) where n is the number of nodes in the tree.
source:
http://www.crazyforcode.com/tree/
IP:
http://packetlife.net/library/cheat-sheets/
IP packet fragmentation
http://mars.netanya.ac.il/~unesco/cdrom/booklet/HTML/NETWORKING/node020.html
No comments:
Post a Comment