raj.kamal.nitj
BAN USER- 0of 0 votes
AnswersGiven a binary tree whose node structures have an extra member to hold an integer value. Fill these with values that is equal to the total number of Left nodes in the left sub-tree minus total number of nodes in right sub tree.
- raj.kamal.nitj in India| Report Duplicate | Flag | PURGE
Software Engineer / Developer Data Structures
#include "stdio.h"
#include "stdlib.h"
#define NUM 13
/* GLOBAL STRUCTURE */
typedef struct Stack Stack;
struct Stack
{
int id;
Stack* next;
Stack* prev;
};
/* GLOBAL VARIABLE */
Stack* top = NULL;
Stack* bot = NULL;
/* GLOBAL FUNCTIONS */
void ArrangeCards(void)
{
int i;
Stack* temp;
for(i=NUM; i>0; i--)
{
temp = (Stack*)malloc(sizeof(Stack));
temp->id = i;
if(top == NULL)
{
temp->next = NULL;
temp->prev = NULL;
top = temp;
bot = temp;
}
else
{
int j; //Num of times bot to top
Stack* iter;
/* Place new card on Top */
temp->next = top;
temp->prev = NULL;
top->prev = temp;
top = temp;
/* Shuffle card */
j = i%(NUM - i + 1);
for(;j>0;j--)
{
//Remove from bottom put it on top
iter = bot;
bot = bot->prev;
bot->next = NULL;
iter->next = top;
iter->prev = NULL;
top->prev = iter;
top = iter;
}
}
}
}
/* MAIN FUNCTION */
int main()
{
Stack* temp;
ArrangeCards();
temp = top;
printf("Card sequence : \n");
while(temp)
{
printf(" %d ", temp->id);
temp = temp->next;
}
printf("\n");
return 0;
}
Output :
rajkamal@Rajkamal-PC:~/Documents/Junk$ ./CardSeq.o
Card sequence :
4 1 13 11 2 10 6 7 3 5 12 9 8
I used modulo to reduce numer of iterations .. but will it be O(nlogn) ??
Sorry it should be total number of nodes in the left sub-tree..
- raj.kamal.nitj July 05, 2012Sorry it should be total number of nodes in the left sub-tree..
- raj.kamal.nitj July 05, 2012
Can be solved using recursion. For each element there arises two choices:
1. Leave the current. Permute rest of array.
2. Swap current with next. Permute rest of array starting from next's next. as both these cannot be used.
Sample code:
- raj.kamal.nitj October 02, 2017