_30_
/ \
10 20
/ / \
50 45 35
The correct solution should print 30, 10, 50, 45, 35, 20.
______30______
/ \
__20__ __40__
/ \ / \
10 25 35 50
/ \ \ /
5 15 28 41
The correct solution should print 30, 20, 10, 5, 15, 28, 35, 41, 50, 40.
_______________28_______________
/ \
4____ ____69
\ /
__8__ __56__
/ \ / \
__7 12__ __34 __27__
/ \ / / \
5_ _13 _2 _3 39
\ / / /
6 11 10 9
correct output of: 28, 4, 8, 7, 5, 6, 11, 10, 9, 39, 27, 56, 69.
Hint:
To solve this problem, you first need to pay attention to these three key areas:
- Printing the leftmost edges from top to bottom. When a node is a leftmost edge, its left child must also be a leftmost edge.
- Printing the leaves from left to right. Remember depth-first traversal?
- Printing the rightmost edges. You would need to print from bottom to top. The key is printing in the opposite order. Easy if you know how to manipulate recursion into a stack-based solution. Remember post-order traversal?
Solution:
We could divide the tree into two subtrees. One is the left subtree, and the other is the right subtree.
For the left subtree, we print the leftmost edges from top to bottom. Then we print its leaves from left to right.
For the right subtree, we print its leaves from left to right, then its rightmost edges from bottom to top.
Printing the leaves from left to right order is a classic example of depth-first traversal. How do you know if a node is a leaf? Easy, if the node does not have both left and right children.
Printing the leftmost edges is just a trivial addition to the depth-first traversal. When a node is a leftmost edge, then its left child must also be a leftmost edge. We could use a variable to pass this information down the tree. Please note that you must add the condition to avoid printing the node twice (a node could be a leftmost edge as well as a leaf node).
Printing the rightmost edges from bottom to top is easy if you realize the trick of manipulating recursion as a stack. Try relate this with how post-order traversal works. When calling recursive functions, function calls are pushed onto a stack, and therefore you could use the implicit stack to your advantage. This trick is especially handy when applied in situation where you need to reverse the order of operations.
#include<stdio.h>
#include<stdlib.h>
struct node {
struct node *left;
struct node *right;
int data;
};
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 printLeftBoundary(node *root) {
if(root==NULL) return;
if(root->left) {
printf("%d ",root->data);
printLeftBoundary(root->left);
}
else if(root->right) {
printf("%d ",root->data);
printLeftBoundary(root->right);
}
}
void printLeafBoundary(node *root) {
if(root) {
printLeafBoundary(root->left);
if(root->left==NULL && root->right==NULL)
printf("%d ",root->data);
printLeafBoundary(root->right);
}
}
void printRightBoundary(node *root)
{
if(root==NULL) return;
if(root->right) {
printRightBoundary(root->right);
printf("%d ",root->data);
}
else if(root->left) {
printRightBoundary(root->left);
printf("%d ",root->data);
}
}
void printBoundary(node *root)
{
if(root)
{
printf("%d ", root->data);
printLeftBoundary(root->left);
printLeafBoundary(root);
printRightBoundary(root->right);
}
}
int main()
{
struct node *root=newnode(1000);
root->left=newnode(500);
root->right=newnode(1500);
root->left->right=newnode(510);
root->left->right->right=newnode(600);
root->left->left=newnode(240);
root->left->left->left=newnode(120);
root->left->left->right=newnode(300);
root->right->left=newnode(1300);
root->right->left->right=newnode(1320);
printBoundary(root);
return 0;
}
Time Complexity
PrintLeftBoundary - O(h), where h is height of tree, log(n) nodes on left are visited once
PrintLeafBoundary - O(n), as each node is visited once
PrintRightBoundary - O(h), where h is height of tree, log(n) nodes on right are visited once.
O(n+2h) total time complexity
