Print boundary of a binary tree. Microsoft Interview.

Print boundary (edge nodes or outside frame) of a binary tree

Microsoft Interview (May 2012) 

Problem Statement

Print outside frame of a binary tree anti-clockwise.
1) Print all left most nodes.
2) Print all leaf nodes.
3) Print all right most nodes.

Please note:

• If a node is a left-most node, then its left child must be a left-most node as well.
• If its left child does not exist, then its right child will be a left-most node.

 Example:
                                    1000
            500                                                1500
    240                510                    1300
120        300                600                   1320

Output:1000 500 240 120 300 600 1320 1300 1500

Algorithm

1) Print root node if it exist.
2) Print left most edges from top to bottom. If a node is a left-most node, then its left child must be a left-most node but if its left child does not exist, then its right child will be a left-most node.

3) Print leaf nodes - a node whose left and right child both are null it is a leaf node.
4) Print right most edges from bottom to top.
    
If you have a different approach in mind, please share it in the comments section.

 Solution

#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