vgeek
BAN USER- 0of 0 votes
AnswersYou are required to parse the xml file:
- vgeek in United States
<ledger>
<person>
<name>Jai</name><location>Bangalore</location>
</person>
<entries>
<entry><day>1</day><credit>50</credit><debit>40</debit></entry>
….
…
multiple entries were there, and multiple people were there.
We were required to validate the XML file.Open and Close tags matching.
We were required to parse, maintain the max balance for each person, the longest span of days each person had the max balance, and report queries such as who had the overall max balance , his span and location. Span must contain the day numbers, not length.| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer - 0of 2 votes
AnswersConvert a base 2 number to a base 4 number
- vgeek in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - -1of 1 vote
AnswersI have heard this question many times in microsoft interviews. Given two arrays find the intersection of those two arrays. Besides using hash table can we attain the same time complexity that is O(m+n) by using some other approach.
- vgeek in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - 0of 0 votes
AnswersGiven a dl representing the spiral level order traversal of a binary tree,convert it to a binary tree using one stack. In Last level, nodes will be either to the right or left only. complete code in C. It is usually done using two stacks. Can it be done using one stack?
- vgeek in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersConsider the problem of sorting in ascending order of an array of numbers where each number is in the range 50000 to 50000000. What sorting algorithm is the best choice for the above problem. What is the best case time complexity of sorting available to this problem.
- vgeek in United States
Options are:
a. Merge Sort
b. Insertion Sort.
c. Quick Sort.
d. Counting Sort.
e. Bubble Sort| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer - 1of 1 vote
AnswersTwo 32-bit integers n and m are given and positions i,j,k,l are given.Write a method to copy the contents of m from position k to l into n from position i to j.
- vgeek in United States
(example n=1010000000,m=10101010,i=3,j=5,k=5,l=7..output=10'101'00000)| Report Duplicate | Flag | PURGE
Microsoft
@Chih.Chiu.19
You have to construct the tree from inorder traversal.
So root would obviously the max element in the array. Then the elements on the left hand side will be on the left subtree and on the right hand side will be on the right subtree. Now to get the root of the left subtree find the max in the left subarray. And to get the root in right find the root in right subarray. Then do this recursively until you get the tree.
@yogi
The test case is above in the code. Suppose the array is:
array=1,5,3,6,2,4. Notice the difference here it is 2,4 instead of 4,2 and it is also a valid inorder traversal as here now 2 becomes the left node of the root 4.
Whereas in the original condition the node 2 comes in the right subtree of root node 4.
Implementation of merge sort is here:
a. Split the linked list into two halves.
b. Call mergesort recursively for both the halves.
c. At last merge the two sorted halves
#include <stdio.h>
#include <stdlib.h>
typedef struct node node_t;
struct node
{
int data;
node_t *next;
};
void push(node_t **head_ref,int data)
{
node_t *n=(node_t *)malloc(sizeof(node_t));
n->data=data;
n->next=(*head_ref);
(*head_ref)=n;
}
void splitLinkedList(node_t *source,node_t **fr,node_t **br)
{
node_t *fast,*slow;
if(source==NULL||source->next==NULL)
{
*fr=source;
*br=NULL;
}
else
{
slow=source;
fast=source->next;
while(fast!=NULL)
{
fast=fast->next;
if(fast!=NULL)
{
slow=slow->next;
fast=fast->next;
}
}
*fr=source;
*br=slow->next;
slow->next=NULL;
}
}
node_t *sortedMerge(node_t *a,node_t *b)
{
node_t *result=NULL;
if(a==NULL)
return b;
else if(b==NULL)
return a;
else if(a->data <= b->data)
{
result=a;
result->next=sortedMerge(a->next,b);
}
else
{
result=b;
result->next=sortedMerge(a,b->next);
}
return result;
}
void mergeSort(node_t **head_ref)
{
node_t *head=*head_ref;
node_t *a,*b;
if(head==NULL||head->next==NULL)
return;
splitLinkedList(head,&a,&b);
mergeSort(&a);
mergeSort(&b);
*head_ref=sortedMerge(a,b);
}
void printList(node_t *head)
{
node_t *temp=head;
while(temp!=NULL)
{
printf(" %d ",temp->data);
temp=temp->next;
}
}
int main()
{
node_t *head=NULL;
push(&head,1);
push(&head,5);
push(&head,3);
push(&head,6);
push(&head,4);
printList(head);
mergeSort(&head);
printf("\n");
printList(head);
}
If the arrays are sorted then you just have to merge the three arrays and then match for the 5 largest numbers . Here is the code.
#include <stdio.h>
#include <conio.h>
int n;
int *topLargestElement(int a1[],int a2[],int a3[])
{
int i=0,j=0,didx=n;
int dest[3*n],top5ele[5];
while(i<n&&j<n)
{
if(a1[i]<=a2[j])
{
dest[didx]=a1[i];
++i;
++didx;
}
else
{
dest[didx]=a2[j];
++j;
++didx;
}
}
if(i<n)
{
while(i<n)
{
dest[didx]=a1[i];
++didx;++i;
}
}
else if(j<n)
{
while(j<n)
{
dest[didx]=a2[j];
++didx;
++j;
}
}
i=0,j=n,didx=0;
while(i<n&&j<3*n)
{
if(a3[i]<=dest[j])
{
dest[didx]=a3[i];
++didx;++i;
}
else
{
dest[didx]=dest[j];
++didx;++j;
}
}
if(i<n)
{
while(i<n)
{
dest[didx]=a3[i];
++didx;++i;
}
}
j=0;
for(i=didx-1;i>=didx-5;i--)
{
top5ele[j]=dest[i];
j++;
}
return top5ele;
}
int main()
{
int a1[]={2,4,9,16,19,68,78};
int a2[]={4,8,67,106,109,115,120};
int a3[]={9,15,19,108,119,130,190};
n=sizeof(a1)/sizeof(a1[0]);
int *arr=topLargestElement(a1,a2,a3);
int i;
printf(" %d %d %d %d %d ",arr[0],arr[1],arr[2],arr[3],arr[4]);
}
Find the max element in the array and it is the root
a. Recursively call for the left side of the array and find max which comes in the left subtree of the root.
b. Recursively call for the right side of the array and that again comes in the right subtree of the root.
c. If there is only one element make the tree node of it and return.
d. If there are two nodes then 2 scenarios arise:
1. If the first element is larger than the other so as it is inorder traversal the first element becomes the root and the next one comes in the right subtree.
2. If the first element is smaller than the other so the other becomes the root and this element comes in the left subarray.
Here is the code:
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
typedef struct tree tree_t;
struct tree
{
int data;
tree_t *left;
tree_t *right;
};
tree_t *newNode(int data)
{
tree_t *n=(tree_t *)malloc(sizeof(tree_t));
n->data=data;
n->left=n->right=NULL;
return n;
}
int findMax(int arr[],int low,int high,int *max)
{
int i,index;
*max=arr[0];
for(i=low;i<=high;i++)
{
if(*max<arr[i])
{
*max=arr[i];
index=i;
}
}
return index;
}
tree_t *constructTree(int arr[],int low,int high,int n)
{
if(low==high)
{
tree_t *root=newNode(arr[low]);
return root;
}
else if(low+1==high)
{
if(arr[low]<arr[high])
{
tree_t *root=newNode(arr[high]);
root->left=newNode(arr[low]);
return root;
}
else if(arr[high]<arr[low])
{
tree_t *root=newNode(arr[low]);
root->right=newNode(arr[high]);
return root;
}
}
int max;
int index=findMax(arr,low,high,&max);
tree_t *root=newNode(max);
if(index<n)
{
root->left=constructTree(arr,low,index-1,n);
root->right=constructTree(arr,index+1,high,n);
}
return root;
}
void inorder(tree_t *root)
{
if(root==NULL)
return;
inorder(root->left);
printf(" %d ",root->data);
inorder(root->right);
}
int main()
{
int arr[]={1,5,3,6,4,2};
int n=sizeof(arr)/sizeof(arr[0]);
int *max;
tree_t *root=constructTree(arr,0,n-1,n);
inorder(root);
}
Used recursion to implement this concept
#include <stdio.h>
#include <stdlib.h>
int stringWildCard(char *first,char *second)
{
if(*first=='\0'&&*second=='\0')
return 1;
else if(*first=='*'&&*(first+1)!='\0'&&*second=='\0')
return 0;
else if(*first=='*'&&*(first+1)!=*second&&*(first-1)!=*second)
return 0;
else if(*first=='*')
return stringWildCard(first+1,second)||stringWildCard(first,second+1);
else if(*first==*second)
return stringWildCard(first+1,second+1);
else if(*first!=*second&&*(first+1)=='*')
return stringWildCard(first+2,second);
else if(*first=='+'&&*(first-1)==*(second-1))
return stringWildCard(first,second+1)||stringWildCard(first+1,second);
return 0;
}
void test(char *first,char *second)
{
stringWildCard(first,second)?puts("Yes"):puts("No");
}
int main()
{
test("b*ba", "bbba");
}
@Venkatesh
str points to the character in the string. I know that there will be recursion stack space. But at every step one condition is being checked and that condition is put to the stack. So the condition is checked n-1 times so n-1 different allocation frames will be there in the stack. Thats I think the same as that of the for loop as there also the code is moving in the loop n times. Correct me if i am wrong
I know that this one could be done by swapping too. That is why i mentioned earlier in my comment. But i am just using a single local variable to reverse the changes. I am not creating the entire string. Its not char str[]. Its char c. And further in swap also you use a local variable like temp to swap the characters. I am using local variable here to store the previous character. Its the same as every time when you call swap function then also a local variable is created to do the required operation.
- vgeek July 24, 2013In place basically means that you dont have to use any extra memory like you should make the changes using only local variable. The complexity would be O(n) because you have to call reverse for every character in the string. Same is the case while swapping the characters of the integers.
- vgeek July 24, 2013Using recursion as:
#include <string.h>
#include <stdio.h>
#include <conio.h>
void stringRev(char str[],int i,int n)
{
static int j;
if(i<n)
{
char ch=str[i];
stringRev(str,i+1,n);
str[j]=ch;
printf("%c",str[j]);
j=j+1;
}
str[j]='\0';
}
int main()
{
char str[]="asd cdfv gfd";
int n=sizeof(str)/sizeof(str[0]);
stringRev(str,0,n);
}
For any palindrome you can consider the cases:
a. If start and end index are same in a string that is i==j then return 1.
b. if at any position i and j string[i]==string[j] and i+1==j then return 2.
c. if at any position i and j string[i]==string[j] then
return longestPalindrome(string,i+1,j-1)+2 //this is the case for 2 length palindromes.
return max(longestPalindrome(string,i,j-1),longestPalindrome(string,i+1,j))
Cant we solve this problem straightaway. I mean if you start with (0,0) and if you have to move to any arbitrary location (i,j) while moving either to the right or bottom in one step then.
Consider the location (3,5) then to reach (3,5) from (0,0) the number of steps are 8 that is 3+5 as you either increase the row number by one or column number by one. So to reach the location (i,j) the number of steps involved are (i+j).Here the shortest path does not matter as you cannot move diagonally .You can only move either right or down. Correct me if i am wrong
If you are give the postfix in an array in the form like
a[]={i,i,n,i,n,n} and another array that denotes the node like
b[]={2,3,4,5,6,7} then you can make the binary tree using recursion as:
tree *makeBinaryTree(char a[],int b[],int *index,int n)
{
int indx=*index;
if(indx==n)
return NULL;
tree *n=makeNewNode(a[indx]);
*index++;
if(b[indx]=='i')
{
n->left=makeBinaryTree(n,a,b,index);
n->right=makeBinaryTree(n,a,b,index);
}
return n;
}
The worst case occurs when the two nodes of the tree lies at the opposite ends that is one node is in the left subtree and the other node is in the right subtree then the number of comparisons required are level-1 where levels the height of the tree. Here we can also apply BFS but its just another technique
- vgeek July 22, 2013Here is the code to solve this problem using array with O(n) time complexity:
a. First for all the words calculate the key value and make an array of the key value. Here key value is calculated by multiplying the integer value of character by 10. Also if the character is uppercase then it is converted to lower case as ARe and are are same words.
b. Now if the words are repeated then they will have the same key value. So now problem reduces to find the number in the array repeated maximum number of times.
c. This is done by taking the count array and initializing it to 0 and further incrementing the count value for every key value of the array taken as index.
d. Then take that key value and then using that key find the corresponding index in the string array. (here it is found by using the space count)
e. Then take that start index and then using that start index print the word till the space is not encountered.
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#define MAX_SIZE 32768
void findRepeatedWord(char str[],int n)
{
int i,k=0;int num=0,numArray[MAX_SIZE];
for(i=0;str[i]!='\0';i++)
{
if(str[i]>=65&&str[i]<=90)
{
str[i]=str[i]+32;
}
if(str[i]!=' ')
{
num=num+10*str[i]-str[i+1];
}
else
{
numArray[k]=num;
k=k+1;
num=0;
}
}
numArray[k]=num;
k=k+1;
int count[MAX_SIZE];
int max_count=0;
for(i=0;i<MAX_SIZE;i++)
{
count[i]=0;
}
for(i=0;i<k;i++)
{
count[numArray[i]]++;
}
int max=count[0],max_index,idx;
for(i=0;i<MAX_SIZE;i++)
{
if(count[i]>max)
{
max=count[i];
max_index=i;
}
}
for(i=0;i<k;i++)
{
if(max_index==numArray[i])
{
idx=i;
break;
}
}
int start_index,count_space=0;
for(i=0;i<n;i++)
{
if(idx==count_space)
{
start_index=i;
break;
}
if(str[i]==' ')
{
count_space=count_space+1;
}
}
printf(" Maximum word repeated is ");
for(i=start_index;str[i]!=' ';i++)
printf("%c",str[i]);
printf(" with %d number of count ",max);
}
int main()
{
char str[]="Are are you are my boy are";
int n=strlen(str);
findRepeatedWord(str,n);
}
I think that your code will not work when for example I enter two node values such that if 8 is a child of node 2 and suppose 6 is a child of node 3 and this node 6 lies in the right subtree of right child of 4 . Then it will return 2 as it will first encounter 8 and then return that node but the least common ancestor of node 8 and 6 would be the parent of node 2 and 3 which is 1.
- vgeek July 21, 2013You can apply the following logic as of binary search although the complexity is linear:
a. Find the middle element of the array
b. In order to find the max difference the indices should be as far as possible. So if arr[mid]>arr[low] find the index difference and if this difference is greater than the difference calculated so far then update this diff.
c. Similarly if arr[high]>arr[mid] find the difference as mentioned above.
d. Also find the difference of arr[high]-arr[low]. Suppose the starting and ending index of the sub-array are such that arr[high]>arr[low] then this would be the max difference
e. Also further check it for low+1,high and also for low,high-1
Below is the code:
#include <stdio.h>
#include <conio.h>
static int diff;
void findMaxDiff(int arr[],int low,int high)
{
if(low==high)
return;
if(low+1==high)
{
if(arr[high]>arr[low])
{
int d=high-low;
if(d>diff)
diff=d;
}
return;
}
else
{
int mid=low+(high-low)/2;
if(arr[mid]>arr[low])
{
int d=mid-low;
if(d>diff)
diff=d;
}
if(arr[high]>arr[mid])
{
int d=high-mid;
if(d>diff)
diff=d;
}
if(arr[high]>arr[low])
{
int d=high-low;
if(d>diff)
diff=d;
}
findMaxDiff(arr,low,high-1);
findMaxDiff(arr,low+1,high);
}
}
int main()
{
int arr[]={65,23,12,43,33,13,67,78,54,21};
int n=sizeof(arr)/sizeof(arr[0]);
findMaxDiff(arr,0,n-1);
printf(" The max j-i diff is %d ",diff);
}
No it will work for all the cases even if the binary tree is not complete as the code that i have pasted is not a complete binary tree and further I am using an indirect recursion call that is a function calling an another function and there printing the result the same function is not being called again and again so need to worry for stack space.
- vgeek July 20, 2013@Chh.Chiu.19
The indices helps us here because we are doing a level order traversal and it is the property of the binary tree that for any node n we have two children whose indices are: For left child 2*n+1 and for right child 2*n+2 . And also the parent of node n lies at the index (n-1)/2 its floor value. And as we have to find the first common parent of two nodes in this question so this property can be made to work. We can also use hash set but i think that could be complex as it will also do the same work as the array is doing here but no doubt hash set can also be used
Check for bst for a given tree. Keep a static previous pointer and do inorder traversal.
a. As inorder traversal gives us a sorted array so if at any point we get the node's value smaller than the previous value than that tree is not a bst.
int checkForBst(tree_t *node)
{
static tree_t *prev=NULL;
if(node)
{
if(!(checkForBst(node->left)
return 0;
if(prev!=NULL&&node->data<=prev->data)
return 0;
prev=node;
return checkForBst(node->right);
}
return 1;
}
Check for bst for a given tree. Keep a static previous pointer and do inorder traversal.
a. As inorder traversal gives us a sorted array so if at any point we get the node's value smaller than the previous value than that tree is not a bst.
int checkForBst(tree_t *node)
{
static tree_t *prev=NULL;
if(node)
{
if(!(checkForBst(node->left)
return 0;
if(prev!=NULL&&node->data<=prev->data)
return 0;
prev=node;
return checkForBst(node->right);
}
return 1;
}
Check for bst for a given tree. Keep a static previous pointer and do inorder traversal.
a. As inorder traversal gives us a sorted array so if at any point we get the node's value smaller than the previous value than that tree is not a bst.
int checkForBst(tree_t *node)
{
static tree_t *prev=NULL;
if(node)
{
if(!(checkForBst(node->left)
return 0;
if(prev!=NULL&&node->data<=prev->data)
return 0;
prev=node;
return checkForBst(node->right);
}
return 1;
}
In order to find the shortest path between any two nodes you have to find the common parent between them that is the least common ancestor.
As it is not a binary search tree so just do a level order traversal and store them in a array then the indexing of the array would be such that for any node of array index n you will have parent at index (n-1)/2 .So for any two nodes just check if they have the same parent. If they have then it is the least common ancestor and the path length is 2 from 1st node to parent and then from parent to second node. If not then iterate upwards until you get a common parent and also increment a path count. I have also uploaded the code for it below.
In order to find the shortest path between any two nodes you have to find the common parent between them that is the least common ancestor.
As it is not a binary search tree so just do a level order traversal and store them in a array then the indexing of the array would be such that for any node of array index n you will have parent at index (n-1)/2 .So for any two nodes just check if they have the same parent. If they have then it is the least common ancestor and the path length is 2 from 1st node to parent and then from parent to second node. If not then iterate upwards until you get a common parent and also increment a path count. I have also uploaded the code for it below.
This is the code for finding least common ancestor in a binary tree:
a. Store the nodes by doing a normal level order traversal
b. And then find the common parent of the node in the array
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
typedef struct tree tree_t;
struct tree
{
int data;
tree_t *left;
tree_t *right;
};
tree_t *newNode(int data)
{
tree_t *n=(tree_t *)malloc(sizeof(tree_t));
n->data=data;
n->left=n->right=NULL;
return n;
}
typedef struct queue q_t;
struct queue
{
int front;
int rear;
int size;
tree_t **array;
};
q_t *newQueue(int size)
{
q_t *q=(q_t *)malloc(sizeof(q_t));
q->front=q->rear=0;
q->array=(tree_t **)malloc(q->size*sizeof(tree_t *));
return q;
}
void enq(q_t *q,tree_t *t)
{
q->array[q->rear++]=t;
}
tree_t *dequeue(q_t *q)
{
q->front++;
return q->array[q->front-1];
}
void printLca(int arr[],int *n,int n1,int n2)
{
int i,parent1,parent2;
int path=2;//path is obviously 2 if both the parents are same
for(i=0;i<*n;i++)
{
if(arr[i]==n1)
{
parent1=(i-1)/2;
}
else if(arr[i]==n2)
{
parent2=(i-1)/2;
}
}
if(parent1==parent2)//if both the parents are same then it is the least common ancestor
{
printf(" The least common ancestor is %d and shortest path is %d",arr[parent1],path);
}
else//iterate until you find a common parent a parent for node n is (n-1)/2 its floor value and also increment the path
{
while(parent1!=parent2)
{
if(parent1<parent2)
{
parent2=(parent2-1)/2;
path=path+1;
}
else if(parent2<parent1)
{
parent1=(parent1-1)/2;
path=path+1;
}
}
printf(" The least common ancestor is %d and shortest path is %d",arr[parent1],path);
}
}
void lca(tree_t *t,int arr[],int n1,int n2,int *index)
{
q_t *q=newQueue(20);
tree_t *temp=t;
while(temp)
{
arr[*index]=temp->data;
(*index)++;
if(temp->left)
enq(q,temp->left);
if(temp->right)
enq(q,temp->right);
temp=dequeue(q);
}
printLca(arr,index,n1,n2);
}
int main()
{
tree_t *t=newNode(1);
t->left=newNode(2);
t->left->left=newNode(4);
t->left->left->left=newNode(8);
t->left->left->right=newNode(10);
t->left->right=newNode(5);
t->left->right->right=newNode(9);
t->right=newNode(3);
t->right->left=newNode(6);
t->right->right=newNode(7);
int arr[30],index=0;
lca(t,arr,8,6,&index);
}
In trie you have for every node 26 pointers that account for the 26 different alphabets. Instead use a ternary search tree which has only three pointers for a particluar node. One if the node value is less than the current value . The middle one if its value is equal to the current value and the third one if its value is more than the current value. In every node you have 4 spaces . One for the three pointers that i mentioned above and one that is 0 or 1 to denote whether we have reached the end of word (a valid one) or not.
a. So put this sentence in a ternary search tree and wherever we find a 1 that is a valid one or the end of a word is reached stop there and print it.
b. In this way continue down until you get 1 in any of the node.
c. But if you found that you have reached the end of a word and the value of the last node is 0 then return false as there is not a valid word else return true
It is catalan number where if n keys are given to us we can generate distinct number of trees from those n keys by the below formula:
No.of.trees= (2n)! / (n!*(n+1)!)
It comes from the fact that if n are the number of keys that for every node we can have 2 children for binary tree then those can be made or mathematically arranged in (2n)!. But for n keys we will have n+1 external nodes. So the internal nodes and external nodes can be arranged seperately in n! and (n+1) !. Note here external nodes cannot be arranged with internal nodes only with external nodes so (n+1)! similarly internal nodes among themselves in n! so for both these arrangements multiply them and divide it by the number of child arrangement to get the required distribution and thus number of different trees that can be generated.
Paste the code and print it. You will get the nodes mirrored at alternate levels. Actually i am recursively passing root->left->left to pass one level down from the current node that is alternate levels similarly root->right->right to get the alternate level in the right side. This further extends down to the below node recursively thus accounting for alternate levels at the next node.
- vgeek July 15, 2013It can be solved using three way partitioning:
#include <stdio.h>
#include <conio.h>
void makeArray(int arr[],int low,int high,int n)
{
int startIndex=0,endIndex=n-1,i,temp;
for(i=0;i<=endIndex;)
{
if(arr[i]<low)
{
temp=arr[i];
arr[i]=arr[startIndex];
arr[startIndex]=temp;
startIndex++;
i++;
}
else if(arr[i]>high)
{
temp=arr[i];
arr[i]=arr[endIndex];
arr[endIndex]=temp;
endIndex--;
}
else
{
i++;
}
}
}
int main()
{
int arr[]={1,14,5,20,4,2,54,20,87,98,3,1,32};
int n=sizeof(arr)/sizeof(arr[0]);
makeArray(arr,20,20,n);
int i;
for(i=0;i<n;i++)
printf(" %d ",arr[i]);
}
This one is the code using recursion
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
typedef struct tree tree_t;
struct tree
{
int data;
tree_t *left;
tree_t *right;
};
tree_t *newNode(int data)
{
tree_t *n=(tree_t *)malloc(sizeof(tree_t));
n->data=data;
n->left=n->right=NULL;
return n;
}
void preorder(tree_t *root)
{
if(root==NULL)
return;
printf(" %d ",root->data);
preorder(root->left);
preorder(root->right);
}
void mirror(tree_t *t)
{
if(t==NULL)
return;
else
{
tree_t *temp;
mirror(t->left);
mirror(t->right);
temp=t->left;
t->left=t->right;
t->right=temp;
}
}
void mirrorAlt(tree_t *t)
{
if(t==NULL)
{
return;
}
else
{
tree_t *temp=t->left;
t->left=t->right;
t->right=temp;
if(t->left==NULL&&t->right==NULL)
return;
else if(t->left!=NULL&&t->right==NULL)
mirrorAlt(t->left->left);
else if(t->right!=NULL&&t->left==NULL)
mirrorAlt(t->right->right);
else
{
mirrorAlt(t->left->left);
mirrorAlt(t->right->right);
}
return;
}
}
int main()
{
tree_t *root=newNode(1);
root->left=newNode(2);
root->left->left=newNode(4);
root->left->right=newNode(5);
root->left->right->left=newNode(6);
root->left->right->right=newNode(7);
root->right=newNode(3);
printf(" Mirror of the tree preorder\n");
mirror(root);
preorder(root);
printf("\nMirror at alternate levels preorder\n");
mirrorAlt(root);
preorder(root);
}
RepGayle L McDowell, CEO at CareerCup
Gayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...
@Chih
- vgeek July 26, 2013Yes the complexity that you mentioned is same. Here i dont think that it can be improved further because in order to construct the tree efficiently that is with right left and right childs you have to find first the max element in the array and the same in the left half and the right half of the array. If you can think of any other approach then it is most welcomed.