fork(2) download
copy 
  1. /* program for boundary traversal of a binary tree */
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. /* A binary tree node has data, pointer to left child
  6.    and a pointer to right child */
  7. struct node
  8. {
  9.     int data;
  10.     struct node *left, *right;
  11. };
  12.  
  13. // A simple function to print leaf nodes of a binary tree
  14. void printLeaves(struct node* root)
  15. {
  16.     if ( root )
  17.     {
  18.         printLeaves(root->left);
  19.  
  20.         // Print it if it is a leaf node
  21.         if ( !(root->left)  &&  !(root->right) )
  22.             printf("%d ", root->data);
  23.  
  24.         printLeaves(root->right);
  25.     }
  26. }
  27.  
  28. // A function to print all left boundry nodes, except a leaf node.
  29. // Print the nodes in TOP DOWN manner
  30. void printBoundaryLeft(struct node* root)
  31. {
  32.     if (root)
  33.     {
  34.         if (root->left)
  35.         {
  36.             // to ensure top down order, print the node
  37.             // before calling itself for left subtree
  38.             printf("%d ", root->data);
  39.             printBoundaryLeft(root->left);
  40.         }
  41.         else if( root->right )
  42.         {
  43.             printf("%d ", root->data);
  44.             printBoundaryLeft(root->right);
  45.         }
  46.         // do nothing if it is a leaf node, this way we avoid
  47.         // duplicates in output
  48.     }
  49. }
  50.  
  51. // A function to print all right boundry nodes, except a leaf node
  52. // Print the nodes in BOTTOM UP manner
  53. void printBoundaryRight(struct node* root)
  54. {
  55.     if (root)
  56.     {
  57.         if ( root->right )
  58.         {
  59.             // to ensure bottom up order, first call for right
  60.             //  subtree, then print this node
  61.             printBoundaryRight(root->right);
  62.             printf("%d ", root->data);
  63.         }
  64.         else if ( root->left )
  65.         {
  66.             printBoundaryRight(root->left);
  67.             printf("%d ", root->data);
  68.         }
  69.        // do nothing if it is a leaf node, this way we avoid
  70.        // duplicates in output
  71.     }
  72. }
  73.  
  74.  
  75. // A function to do boundary traversal of a given binary tree
  76. void printBoundary (struct node* root)
  77. {
  78.     if (root)
  79.     {
  80.         printf("%d ",root->data);
  81.  
  82.         // Print the left boundary in top-down manner.
  83.         printBoundaryLeft(root->left);
  84.  
  85.         // Print all leaf nodes
  86.         printLeaves(root->left);
  87.         printLeaves(root->right);
  88.  
  89.         // Print the right boundary in bottom-up manner
  90.         printBoundaryRight(root->right);
  91.     }
  92. }
  93.  
  94. // A utility function to create a node
  95. struct node* newNode( int data )
  96. {
  97.     struct node* temp = (struct node *) malloc( sizeof(struct node) );
  98.  
  99.     temp->data = data;
  100.     temp->left = temp->right = NULL;
  101.  
  102.     return temp;
  103. }
  104.  
  105. // Driver program to test above functions
  106. int main()
  107. {
  108.     // Let us construct the tree given in the above diagram
  109.     struct node *root         = newNode(20);
  110.     root->left                = newNode(8);
  111.     root->left->left          = newNode(4);
  112.     root->left->right         = newNode(12);
  113.     root->left->right->left   = newNode(10);
  114.     root->left->right->right  = newNode(14);
  115.     root->right               = newNode(22);
  116.     root->right->right        = newNode(25);
  117.  
  118.     printBoundary( root );
  119.  
  120.     return 0;
  121. }
Success #stdin #stdout 0.01s 1808KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
20 8 4 10 14 25 22
https://ideone.com/5Mdp7
language:
C (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!