CareerCup

PrintBorder(Node root)
{
    PrintNode(root);
    PrintBorderInternal(root.Left, true /* is border */, 0 /* left branch */);
    PrintBorderInternal(root.Right, true /* is border */, 1 /* right branch */);
}

// direction = 0 for left, 1 for right
PrintBorderInternal(Node node, bool isBorder, int direction)
{
    if (node == null)
        return;

    // If the node is a LEAF node, or is a border, print it.
    if (isBorder || (node.Left == NULL && node.Right == NULL))
    {
        PrintNode(node);
    }

    PrintBorderInternal(Node.Left, isBorder && direction == 0, direction);
    PrintBorderInternal(Node.Right, isBorder && direction == 1, direction);
}

Do an in order traversal of the tree and build a LinkedHashMap of nodes at each level. For level 0, there will only be one node. For the last level all nodes are in the border. For all internal levels first and last nodes are on the border.

Complexity of time and space is O(n). You can optimize the space complexity further but another time

Do a BFS... At every point print first and last Node. Except last where you will priont the whole Queue. Although order will be little different then you mentioned but even that is easy to format by maintaining the list of border nodes instead of printing right away.
Time complexity o(n) space complexity is O(log n)

Keep printing all the elements in extreme left and all the elements in extreme right and leaf node.
Leave those elements which come from moving left to right or right to left.

Here is a code for the same

void display(struct node* root, int left, int right)
{
if( (left) || (right) || !((root->right)||(root->left)) )
printf("%d\n",root->data);
return;
}

void findborder(struct node* root, int left, int right)
{

if(root != NULL)
{
display(root,left,right);
findborder(root->left,left&1,0);
findborder(root->right,0,right&1);

}

else
{
return 0;
}

}