Interview Question
Country: United States
To print in the right order, wouldn't you need to do the "if (isBorder) print" before the recursive calls if direction is left, and after the calls if the direction is right?
At the root node, use preorder for the left side, and use postorder in the right side, then the output will be in the correct order.
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;
}
}
- Anonymous May 15, 2012