sumit.083
BAN USERWe can check for inorder traversal of both the tree simultaneously within the same function
Let us suppose we iterate the main tree in preorder traversal such that we have the head node of the subtree and the current node of the main tree to have the same values.
Now call the following function
bool SearchSubtree(tree * HeadMain , tree* HeadSubtree) // HeadMain->value = HeadSubtree->value
{
If (!HeadSubtree)
return true;
if ((HeadMain == NULL || HeadMain != HeadSubtree) && (HeadSubtree != NULL))
return false;
if ((SearchSubtree(HeadMain->left , HeadSubtree->left)) == false)
return false;
return (SearchSubtree(HeadMain->left , HeadSubtree->left)) == false) ;
}
So what I'm trying to do is
1)Check if the nodes do not match , subtree is not present
2)If the nodes match , check the left subtree of both
3)Then check the right subtree
4)Now we dont have to traverse the Main tree completely . Eg. We'll keep on calling the left child of the main tree recursively only to the point the left child of the subtree has been completely traversed . We recursively call back the previous nodes for both . In essence we are traversing only that part of the main tree which is concerned with the subtree .
5)Extra memory is saved from copying each elsement and checking them later
6)The complexity O(N) where n corresponds to the number of elements of the subtree
typedef struct tree {
int val,
struct tree *left;
struct tree *right;
} tree_t;
tree_t * FindLargest(tree_t* node) {
if (NULL == node)
return NULL;
tree_t * left_largest = FindLargest(node->left);
tree_t * right_largest = FindLargest(node->right);
if (NULL == left_largest && NULL == right_largest)
return node;
if (NULL != left_largest && NULL ! = right_largest) {
if ((node->val > right_largest->val) && (node->val > left_largest->val))
return node;
else if (right_largest->val > node->val) && (right_largest->val > left_largest->val))
return right_largest;
else
return left_largest;
}
if (left->largest == NULL)
return (node->val > right_largest->val ? node : right_largest);
else
return (node->val > left_largest->val ? node : right_largest);
}
Basically I'm trying to compare the values of the parent , its left child and right child.
1) If no child is parent , the largets value is of its parent.
2)if both the children are present , return the largest value among the parent and the children
3)If either of the children is present , do the same as case 2
So from each subtree I'm getting the highest value recursively
int MaximumProduct(int * arr)
{
int * a = NULL;
int * b = NULL;
int * c = NULL;
int * d = NULL;
int * e = NULL;
for (int i =0 ; i < sizeof(arr)/sizeof(arr[0]); i++) {
if (arr[i] < 0) {
if (NULL == d) {
d = new int (a[i]);
}
else if (NULL == e) {
if (*d > a[i]) {
e = new int(*d);
*d = a[i];
}
else {
*e = arr[i];
}
}
else if (arr[i] < *d) {
*e = *d;
*d = arr[i];
}
else if (arr[i] < *e) {
*e = arr[i];
}
} // end of negative number check
else {
if (a!=NULL && b!=NULL && c!=NULL) {
if (arr[i] > *a) {
*c = *b;
*b = *a;
*a = arr[i];
}
else if (arr[i] > *b) {
*c = *b;
*b = arr[i];
}
else if (arr[i] > *c) {
*c = arr[i];
}
continue;
}
if (NULL == a) {
a = new int (arr[i]);
}
else if (NULL == b) {
if (arr[i] > *a) {
b = new int(a);
*a = arr[i];
}
}
else if (NULL == c) {
if (arr[i] > *a) {
c = new int(*b);
*b = *a;
*a = arr[i];
}
else if(arr[i] > b) {
c = new int(*b);
*b = arr[i];
}
else {
c = new int (arr[i]);
}
}
}
return ( (a*b)*c > (a*d)*e ? (a*b)*c : (a*d)*e);
}
Shouldn't we check the max size of the queue ? Suppose the maximum size of the queue is MAX_SIZE . If there are n elements already present in outbox , should'nt we allow only (MAX_SIZE - n) elements in inbox
- sumit.083 May 06, 2014