Sunday, August 10, 2014

dumps

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

No comments:

Post a Comment