Question: Write a program to find the anti-clock-wise peripheral (boundary) of a complete tree.

Answer: For a complete tree peripheral (boundary) is defined as
  • First the root
  • Then nodes on left edge
  • Then leaf nodes
  • Then nodes on right edge

For the above tree, peripheral will be

0 1 3 7 8 9 10 11 12 13 14 6 2

Algorithm:
  • print root node
  • print left nodes and leafs of left subtree in same order
  • print leafs and right nodes of right subtree in same order
Code:

  
enum {LEFT, RIGHT, LEAF};

bool isleaf(struct node* tree)
{
return (!(tree->left || tree->right));
}

void rperipheral (struct node* root, int state)
{
if(root)
{
switch (state)
{
case LEFT:
printf("\t %d", root->data);
rperipheral(root->left, LEFT);
rperipheral(root->right, LEAF);
break;
case RIGHT:
rperipheral(root->left, LEAF);
rperipheral(root->right, RIGHT);
printf("\t %d", root->data);
break;
case LEAF:
if (isleaf(root))
printf("\t %d", root->data);
rperipheral(root->left, LEAF);
rperipheral(root->right, LEAF);
break;
}
}
}

void peripheral (struct node* root)
{
printf("%d",root->data);
rperipheral(root->left, LEFT);
rperipheral(root->right, RIGHT);
}


Time complexity of the above solution is O(n) as every node is traversed just once.

PS: Above solution can be extended to incomplete trees as well with small modifications. But one must be clear to define the boundary in case of incomplete tree.

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.