Sep 232012
 

Given a Binary Tree. Write code to print the boundary nodes of the Tree. For example, if the Binary tree is

           __30__
         /       \
       /          \
      20          40
    /    \      /   \
  10     25    35   50
 /  \      \        /
5   15      28    41

The output should be: 30  20  10 5  15  28  35  41  50  40.

           A
         /   \
        B     C
      /   \    \
     D     E    F
          / \
         G   H

The output should be: A  B  D  G  H  F  C

Solution:
The Edge Nodes (or Boundary Nodes) basically can be divided into three parts:

  1. All the Nodes in the left most edge of the tree
  2. All the leaf nodes
  3. All the Nodes in the Right-most Edge of the tree

The Algorithm will be on the same line:

1. Print Left Boundary nodes in Top-Down order.
2. Print all the leaf nodes (in Left-to-Right order).
3. Print Right Boundary nodes in Bottom-Up order.

Code:

Lets write the code of above 3 sections separately. First the code to print the Left most boundary of the tree.

This function will not print the last node (which is a leaf node) in the left boundary, because it will be anyway get printed along with the leaf nodes (2nd function).

All the three functions uses Recursion. This one uses Tail-Recursion.

/** Function to print Nodes in the Left Boundary 
 * in Top-Down manner.
 */  
void printLeftBoundary(Node* root)
{
    // We won't print the last Node (leaf) in the left boundary.
    // Because that node will be print when we will print leaf nodes.
    if( (root == NULL) || (root->lptr==NULL && root->rptr==NULL) )  
        return; 

    printf("%d ", root->data);

    // If Node has left pointer, then it is the boundary.
    // Else the right pointer will be part of boundary.
    if (root->lptr)
        printLeftBoundary(root->left);
    else if( root->right )
        printLeftBoundary(root->right);
}

Function to print the Leaf nodes is similar to Counting the leaf nodes or Printing the Non-leaf Nodes:

/** Function to Print the leaf nodes from Left to Right.
 */ 
void printLeaveNode(Node* root)
{
    if( root == NULL )
        return;

    if ( (root->lptr == NULL)  &&  (root->rptr == NULL) )
        printf("%d ", root->data);

    printLeaveNode(root->lptr);
    printLeaveNode(root->rptr);
}

Function to print the Right boundary will also be similar to the function to print the left boundary (won’t print the last leaf node in the right boundary). Except, it uses Head-Recursion.

/** Function to print Nodes in the Right Boundary 
 *  in Bottom-Up manner.
 * 
 *  Using Head-recursion 
 *  (Calling the function recursively first and then printing)  
 */  
 void printRightBoundary(Node* root)
{
    if(root == NULL || (root->lptr==NULL && root->rptr==NULL) )
        return;

    if ( root->rptr )
        printRightBoundary(root->right);
    else if ( root->lptr )
        printRightBoundary(root->left);

    printf("%d ", root->data);
}

Lets also write the function which calls above 3 functions is right order.

void printEdgeNodes(Node* root)
{
    if(root == NULL ) { return; }

    printf("%d ",root->data);
    printLeftBoundary(root->left);

    // Printing leaf nodes in Left to Right order.
    printLeaveNode(root->left);
    printLeaveNode(root->right);

    printRightBoundary(root->right);
}

I know there is no need to mention that the structure Node of the Binary tree used above is as follows:

struct Node
{
    int data;
    Node* lptr; // Left sub-tree
    Node* rptr; // Left sub-tree
};

  2 Responses to “Print edge nodes (boundary nodes) of a Binary Tree”

Comments (2)
  1. a little correction in printLeaveNode() function……second conditon should be.
    if ( (root->lptr == NULL) && (root->rptr == NULL) ).

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)