CareerCup

where will the root go?

anyways, may be we can maintain 3 arrays and while BFS, fill those arrays and after BFS print those.

i guess root will come at the last I guess... so if we have:
1
/ \
2 3
/ \ /
4 5 6

@Tim .. Then u mean we should print: 2 4 5 6 3 1 ?

Probably considering a bigger tree is better to analyse this question:
{{
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ \
8 9 10 11 13
\
12

}}}
Then order shud be: 2 4 8 9 10 12 5 11 3 6 13 7 1
Is my ordering correct ? (or 4 shud cum b4 2 ? :o)

(oops.. ignore previous drawing..)

Probably considering a bigger tree is better to analyse this question:

1
                            /               \
			   2	             3
                        /      \           /   \
		       4        5	  6     7
		      /  \     /  \        \
 		     8	  9  10   11        13
				   \
				    12

Then order shud be: 2 4 8 9 10 12 5 11 3 6 13 7 1
Is my ordering correct ? (or 4 shud cum b4 2 ? :o)

Shouldn't the order be : 2 4 8 9 10 12 5 11 6 13 7 3 1 ..??

guys..here is a good solution and fair one.I copied frm id = 3747687

void printOuterTree(Node root){
if(root != null){
System.out.println(root.element);
printOuterTree(root.left,1,1);
printOuterTree(root.right,0,0);
}
}

void printOuterTree(Node root,int urFlag, int parentFlag){
if(root == null)
return;
if(root.left == null && root.right == null)
System.out.println(root.element);
else{

if(urFlag==1){//do a preorder for left subtree

if(urFlag == parentFlag)
System.out.println(root.element);
printOuterTree(root.left,1,urFlag);
printOuterTree(root.right,0,urFlag);
}
else{//do a post order for right sub tree
printOuterTree(root.left,1,urFlag);
printOuterTree(root.right,0,urFlag);
if(urFlag == parentFlag)
System.out.println(root.element);
}
}
}

I am not able to get what the question is ?

Will DFS doesn't work for this ?

Tried to take care of most of the cases. Here's the bfs algo

void bfs (Node *root)
{
    Queue q;
    int next_level;
    int current_level;
    int i = 0; j = 0; k = 0, current_level_holder;
    Node left[MAX], right[MAX], leaf[MAX];
    if (root != NULL)
    {
        q.enqueue (root);
        current_level = 1;   //No of nodes left at the current level
        next_level = 0;      //keeps count of no of nodes at the next level;
        current_level_holder = 1;   //Used for comparison and meet certain conditions
        left[i++] = root;
        while (!q.isEmpty ())
        {
            if (current_level == 0)
            {
                current_level = next_level;
                current_level_holder = next_level;
                next_level = 0;
            }
            root = q.dequeue;
            if (root->left)
            {
                if (next_level == 0 && current_level == current_level_holder && (root->left->left
                != 0 || root->left->right != 0))
                    left[i++] = root->left;
                next_level++;
                q.enqueue (root->left);
            }
            current_level_holder--;
            if (root->right)
            {
                if (current_level == 1 && (next_level != 1 || root == head))
                    right[j++] = root->right;
                q.enqueue (root->right);
                next_level++;
            }
            current_level_holder--;
            if (root->left == NULL && root->right == NULL)
                leaf[k++] = root;
            current_level--;
        }
    }
}
Print the left and leaf arrays as is and print the right array backwards

- Just print the root first.
- Then pass left child to your bfs method.
- Then pass right child to your bfs method.

Isn't this postorder traversal?

1. print root
2. print pre-order of the left subtree with:
a. a node is printed if it reached only by traversing left children (if the traversal never makes a right move),
b. or if it is a leaf
3. print post-order of the right subtree with:
a. a node is printed if it reached only by traversing right children(if the traversal never makes a left move),
b. or if it is a leaf

void printLeftSide( tree* root, bool toPrint )
{
if(root==NULL) return ;
if((root->left==NULL && root->right==NULL)|| toPrint) printf("%d ",root->data);
printLeftSide(root->left,toPrint);
printLeftSide(root->right,false);
}
void printRightSide( tree* root, bool toPrint )
{
if(root==NULL) return ;
printRightSide(root->left,false);
printRightSide(root->right,toPrint);
if((root->left==NULL && root->right==NULL)|| toPrint) printf("%d ",root->data);
}
void printBoundary( tree* root )
{
if(!root) printf("%d ",root->data);
printLeftSide(root->left,true);
printRightSide(root->right,true);
}
int main()
{
tree *T = newNode(26);
T->right = newNode(3);
T->right->right= newNode(3);
T->left = newNode(10);
T->left->left = newNode(4);
T->left->left->right = newNode(30);
T->left->right = newNode(6);
printBoundary(T);
puts("");
return 0;
}