Advaita11
BAN USERTh above problem can be solved using 2 queues and a stack.
Let the two queues be q1 and q2 and the stack be s.
Initialize a variable flag hat determines the order for each level with 0
Firstly put the root in q1
Now do as follows :
For each level i
1) Dequeue from q1 and push its left and right child into the stack s. Also enqueue this dequeued item into q2
2)Now once you are done with pushing all the children for this level, pop two items from stack for a single dequeued item from q2 var_q2. Now you have two items from stack that will become children of dequeued item from q2
if(flag == 1){
// for this level
// first set right child of q2_var
// then set left child of q2_var
// finally put left child and then right child of q2_var back to q1
// flag = 0;
}
else {
// for this level
// first set left child of q2_var
// then set right child of q2_var
// finally put left child and then right child of q2_var back to q1
// flag = 0;
}
// Repeat this procedure until q1 is Empty
Here is a working code for the above problem
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
struct BTreeNode{
char ch;
struct BTreeNode *left;
struct BTreeNode *right;
}BTreeNode;
struct BTreeNode * buildTree(){
struct BTreeNode *root;
root = new struct BTreeNode;
root->left = root->right = NULL;
root->ch = 'a';
root->left = new struct BTreeNode;
root->left->ch = 'b';
root->right = new struct BTreeNode;
root->right->ch = 'c';
root->left->left = new struct BTreeNode;
root->left->left->ch = 'd';
root->left->right = new struct BTreeNode;
root->left->right->ch = 'e';
root->right->left = new struct BTreeNode;
root->right->left->ch = 'f';
root->right->right = new struct BTreeNode;
root->right->right->ch = 'g';
root->left->left->left = new struct BTreeNode;
root->left->left->left->ch = 'h';
root->left->left->right = new struct BTreeNode;
root->left->left->right->ch = 'i';
root->left->right->left = new struct BTreeNode;
root->left->right->left->ch = 'j';
root->left->right->right = new struct BTreeNode;
root->left->right->right->ch = 'k';
root->right->left->left = new struct BTreeNode;
root->right->left->left->ch = 'l';
root->right->left->right = new struct BTreeNode;
root->right->left->right->ch = 'm';
root->right->right->left = new struct BTreeNode;
root->right->right->left->ch = 'n';
root->right->right->right = new struct BTreeNode;
root->right->right->right->ch = 'o';
return root;
}
void level_order(struct BTreeNode *root){
queue<struct BTreeNode *> q;
struct BTreeNode *temp;
q.push(root);
q.push(NULL);
while(!q.empty()){
temp = q.front(); q.pop();
if(q.empty()) break;
if(temp == NULL) {cout<<"\n"; q.push(NULL); }
else{
cout<<temp->ch<<" ";
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
}
}
cout<<"\n";
}
void alternate_nodes(struct BTreeNode *root){
int flag = 0;
struct BTreeNode *temp;
stack<struct BTreeNode *> s;
queue<struct BTreeNode *> q1,q2;
q1.push(root);
while(1){
if(q1.empty()) break;
while(!q1.empty()){
q2.push(q1.front());
temp = q1.front(); q1.pop();
if(temp->left) s.push(temp->left);
if(temp->right) s.push(temp->right);
}
if(flag == 1){
while(!q2.empty()){
if(s.empty()) break;
temp = q2.front(); q2.pop();
temp->right = s.top(); s.pop();
if(s.empty()) break;
temp->left = s.top(); s.pop();
if(temp->left) q1.push(temp->left);
if(temp->right) q1.push(temp->right);
}
flag = 0;
}
else{
while(!q2.empty()){
if(s.empty()) break;
temp = q2.front(); q2.pop();
temp->left = s.top(); s.pop();
if(s.empty()) break;
temp->right = s.top(); s.pop();
if(temp->left) q1.push(temp->left);
if(temp->right) q1.push(temp->right);
}
flag = 1;
}
}
level_order(root);
}
int main()
{
struct BTreeNode *root;
root = buildTree();
level_order(root);
alternate_nodes(root);
return 0;
}
Best way to do that
- Advaita11 June 28, 2014