WAP Print Edge Nodes (Boundary) of a Binary Tree

Print all edge nodes of a complete binary tree anti-clockwise.
That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes.
In other words, print the boundary of the tree.

Variant: Print the same for a tree that is not complete.


______30______
/ \
__20__ __40__
/ \ / \
10 25 35 50
/ \ \ /
5 15 28 41


o/p 30, 20, 10, 5, 15, 28, 35, 41, 50, 40.




50 17 12 9 14 19 67 76 72

similerly for this tree


/* program to check if a tree is height-balanced or not */
#include
#include
#define bool int

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}


void printLeftEdges(node *p, int print) {
if (!p) return;
if (print || (!p->left && !p->right))
printf(" %d",p->data);
printLeftEdges(p->left, print);
printLeftEdges(p->right, (print && !p->left ? 1: 0));
}

void printRightEdges(node *p, int print) {
if (!p) return;
printRightEdges(p->left, (print && !p->right ? 1: 0));
printRightEdges(p->right, print);
if (print || (!p->left && !p->right))
printf(" %d", p->data);
}

void printOuterEdges(node *root) {
if (!root) return;
printf(" %d ", root->data);
printLeftEdges(root->left, 1);
printRightEdges(root->right, 1);
}

int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->left->left = newNode(8);
root->right->left=newNode(6);
root->right->right=newNode(7);
root->right->left->left=newNode(9);
root->right->right->right=newNode(10);

printOuterEdges(root);

getchar();
return 0;
}


2nd Method

its Awesome & Cool Solution

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */

enum {LEFT, RIGHT, LEAF};


struct node
{
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}



int 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);
}



int main()
{
struct node *root = newNode(0);
root->left = newNode(1);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(4);
root->left->left->left = newNode(5);
root->left->right->right = newNode(6);
root->left->right->left = newNode(7);
root->left->right->right = newNode(8);
root->right->left = newNode(13);
root->right->right = newNode(14);
root->right->left->left = newNode(9);
root->right->left->right = newNode(10);
root->right->right->left = newNode(11);
root->right->right->right = newNode(12);

peripheral(root);


return 0;

}

Time Complexity O(N)
Space Complexity O(1)
Run here https://ideone.com/MUb3L