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.
Very nice!
We can solve this by making a level order traverse of this tree, in each level, print the first and last node - to get the last node, we can put a special node to mark the end of one level, and print all leaf nodes in one level.
This seems easier to implement and understand.
@YuanYun.Kenny.CN: But your order should be first all left nodes, then leaf nodes and then all right nodes in reverse order. How will you achieve that in level order traversal?
Hi, Akash
Thanks for your reply.
I didn't notice the requirement about the order "anti-clock-wise".
For a complete tree, we can put all the last nodes of each level into a stack, after print the leaf nodes of the last level, then pop all right nodes from the stack.
But my solution would require extra space, and be only applicable for full/complete trees.
Now I can understand your solution is much better :)
Hey Akash,
Can't this be simple?
First print the left most path
root=treeRoot;
while(root!=NULL)
{
print(root->data);
root=root->left;
}
then printLeafNodes();
then recursively print(treeRoot->right)
which is O(n) - who traverse the left most and right most path twice.