Boundary Traversal of binary tree | C program for boundary traversal of a binary tree ; A binary tree node has data , pointer to left child and a pointer to right child ; A simple function to print leaf nodes of a binary tree ; Print it if it is a leaf node ; A function to print all left boundary nodes , except a leaf node . Print the nodes in TOP DOWN manner ; to ensure top down order , print the node before calling itself for left subtree ; do nothing if it is a leaf node , this way we avoid duplicates in output ; A function to print all right boundary nodes , except a leaf node Print the nodes in BOTTOM UP manner ; to ensure bottom up order , first call for right subtree , then print this node ; do nothing if it is a leaf node , this way we avoid duplicates in output ; A function to do boundary traversal of a given binary tree ; Print the left boundary in top - down manner . ; Print all leaf nodes ; Print the right boundary in bottom - up manner ; A utility function to create a node ; Driver program to test above functions
#include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE struct node { int data ; struct node * left , * right ; } ; void printLeaves ( struct node * root ) { if ( root == NULL ) return ; printLeaves ( root -> left ) ; if ( ! ( root -> left ) && ! ( root -> right ) ) printf ( " % d ▁ " , root -> data ) ; printLeaves ( root -> right ) ; } void printBoundaryLeft ( struct node * root ) { if ( root == NULL ) return ; if ( root -> left ) { printf ( " % d ▁ " , root -> data ) ; printBoundaryLeft ( root -> left ) ; } else if ( root -> right ) { printf ( " % d ▁ " , root -> data ) ; printBoundaryLeft ( root -> right ) ; } } void printBoundaryRight ( struct node * root ) { if ( root == NULL ) return ; if ( root -> right ) { printBoundaryRight ( root -> right ) ; printf ( " % d ▁ " , root -> data ) ; } else if ( root -> left ) { printBoundaryRight ( root -> left ) ; printf ( " % d ▁ " , root -> data ) ; } } void printBoundary ( struct node * root ) { if ( root == NULL ) return ; printf ( " % d ▁ " , root -> data ) ; printBoundaryLeft ( root -> left ) ; printLeaves ( root -> left ) ; printLeaves ( root -> right ) ; printBoundaryRight ( root -> right ) ; } struct node * newNode ( int data ) { struct node * temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ; temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } int main ( ) { struct node * root = newNode ( 20 ) ; root -> left = newNode ( 8 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 12 ) ; root -> left -> right -> left = newNode ( 10 ) ; root -> left -> right -> right = newNode ( 14 ) ; root -> right = newNode ( 22 ) ; root -> right -> right = newNode ( 25 ) ; printBoundary ( root ) ; return 0 ; }