sriparna.c35
BAN USERFollowing is a non-recursive approach :
#define TRUE 1
#define FALSE 0
int isFoldable(Node * head){
char [] leftSequence = left_to_right_preorder(head->left_child);
char [] rightSequence = right_to_left_preorder(head->right_child);
if(is_equal(leftSequence, rightSequence)){
return TRUE;
}
return FALSE;
}
char[] left_to_right_preorder(Node * node){
Queue queue;
enqueue_left_to_right_in_queue(&queue, node);
char result[queue.size() + 1];
result[0] = queue.size();
for(int i = 1;i <= queue.size(); i++){
result[i] = queue.pop().value;
}
return result;
}
void enqueue_left_to_right_in_queue(Queue * queue, Node * node){
if(node != null){
queue.push(node);
enqueue_left_to_right_in_queue(queue, node->left);
enqueue_left_to_right_in_queue(queue, node->right);
}
}
char[] right_to_left_preorder(Node * node){
Queue queue;
enqueue_right_to_left_in_queue(&queue, node);
char result[queue.size()+ 1] ;
result[0] = queue.size();
for(int i = 1 ; i <= queue.size(); i++){
result[i] = queue.pop().value;
}
return result;
}
void enqueue_right_to_left_in_queue(Queue * queue, Node * node){
if(node != null){
queue.push(queue, node);
enqueue_right_to_left_in_queue(queue, node->right_child);
enqueue_right_to_left_in_queue(queue, node->left_child);
}
}
int is_equal(char* first, char* second){
if(first[0] != second[0]){
return 0;
}
for(int i = 1; i <= first[0]; i++){
if(first[i] != second[i]){
return 0;
}
}
return 1;
}
Apologies for the multiple entries..
- sriparna.c35 May 11, 2015typedef struct Node{
int value;
char type;
struct Node * left_child;
struct Node * right_child;
}Node;
Queue queue;
Stack stack;
void printZigZag(Node * head){
if(head == null){
return;
}
queue.push(head);
int row_number = 0;
int num_of_elements = 1;
int elements_covered_so_far = 0;
while(queue.size != 0){
Node * node = queue.pop();
if(node.type == PLACE_HOLDER){
continue;
}
elements_covered_so_far ++;
if(elements_covered_so_far == num_of_elements){
Node * place_holder = (Node*)malloc(sizeof(Node));
place_holder.type == PLACE_HOLDER;
queue.push(place_holder);
elements_covered_so_far = 0;
num_of_elements = num_of_elements * 2;
row_number++;
}
queue.push(node->left_child);
queue.push(node->right_child);
if(row_number % 2 ==1){
//print in reverse order
stack.push(node);
}
else{
printf("%d ",node->value);
}
if(stack.size() == num_of_elements){
while(!stack.is_empty()){
Node * node = stack.pop();
printf("%d ",node->value);
}
}
}
}
- sriparna.c35 May 11, 2015