Boundary Traversal of Binary tree

The boundary traversal of the binary tree consists of the left boundary, leaves, and right boundary without duplicate nodes as the nodes may contain duplicate values. There are two types of boundary, i.e., left boundary and right boundary. The left boundary can be defined as the path from the root to the left-most node, whereas the right boundary can be defined as the path from the root to the right-most node. If the root node does not contain any left and right subtree, then the root node itself would be considered as the left boundary and right boundary.

Let’s understand the boundary traversal of binary tree through an example.

Consider the below tree:

We have to perform a boundary traversal in the above binary tree. First, we traverse all the nodes that appear on the left in the above binary tree that comes under the boundary traversal. The nodes that appear on the left are a b c d f e. The nodes that appear on the right are a k l n. We have traversed the left and right nodes, and now we will traverse the leaf nodes. In the above tree, the leaf nodes are e g h j m n. Some of the nodes repeated in all the boundaries; for example, node ‘a’ appears in both left and right boundary, so we will remove ‘a’ from the right boundary, and now it appears only once. Some of the nodes are also repeated in leaf nodes. Since node ‘e’ appears in both left boundary and leaf node so we will remove ‘e’ from the leaf node. The node ‘n’ also appears in both right boundary and leaf node, so we will remove the node ‘n’ from the leaf node. Therefore, the final boundary traversal of tree would be:

a b c d f e k l n g h j

Suppose we want to perform boundary binary tree traversal in an anti-clockwise direction, then the problem is broken down into four parts:

First root would be printed.
The leftmost nodes except the leaf nodes would be traversed.
Leaf nodes
The rightmost nodes except the leaf nodes would be traversed.

Source code to find leftmost nodes in a binary tree given below:

  void left_boundary_tree(node *p)  {      if(p)     {           if(p->left)           {             print(p->data);             left_boundary_tree(p->left);          }     }  else if(p->right)  {      print(p->data);     left_boundary_tree(p->right);  }  }  In the above, the pointer p which is passed to the function is the pointer that points to the root node of the binary tree. If the current node has a left node then the condition p->left would be true. It will print the current node data and the pointer p moves to the left of the current node data. The function left_boundary_tree(p->left); calls itself till wee find the left node.  

Source code to find rightmost nodes in a binary tree given below:

  void right_boundary_tree(node *p)  {      if(p)     {           if(p->right)           {             print(p->data);             right_boundary_tree(p->right);          }     }  else if(p->left)  {      print(p->data);     right_boundary_tree(p->left);  }  }  

Source code to print the leaf nodes.

  void print_leaf_node(node *p)  {     if(p)    {         print_leaf(p->left);        if((!p->left) && !(p->right))        {             print(p->data);        }    print_leaf(p->right);    }  }  

Below is the C implementation for the boundary traversal of a binary tree

  /* C program for boundary traversal   of a binary tree */      #include   #include       /* Creation of user-defined structure named as node that has data, pointer to left child  and a pointer to right child */    struct node {      int data;      struct node *left, *right;  };      // A function that prints all the leaf nodes of a binary tree  void print_Leaf(struct node* root)  {      if (root == NULL)          return;          print_Leaf(root->left);          // Condition would be true if the node does not have any left and right child.      if (!(root->left) && !(root->right))          printf(“%d “, root->data);          print_Leaf(root->right);  }      // A function that prints all the left boundary nodes, except a leaf node.  // Print the nodes in from the top to the bottom manner  void print_left_boundary(struct node* root)  {      if (root == NULL)          return;          if (root->left) {              // print the root data before calling the function itself in a top-down manner.                    printf(“%d “, root->data);          print_left_boundary(root->left);      }      else if (root->right) {          printf(“%d “, root->data);          print_left_boundary(root->right);      }        // if the node is a leaf node then we do not need to do anything otherwise it will create duplicacy..  }    // A function that prints all the left boundary nodes, except a leaf node.  // Print the nodes in from the bottom to the top manner    void print_right_boundary(struct node* root)  {      if (root == NULL)          return;          if (root->right) {          // First, we will call the right subtree in order to maintain the bottom to top approach.          print_right_boundary(root->right);          printf(“%d “, root->data);      }      else if (root->left) {          print_right_boundary(root->left);          printf(“%d “, root->data);      }  // if the node is a leaf node then we do not need to do anything otherwise it will create duplicacy..    }      // A function to do boundary traversal of a given binary tree  void print_boundary_nodes(struct node* root)  {      if (root == NULL)          return;          printf(“%d “, root->data);          // Print the left boundary in top-down manner.      print_left_boundary(root->left);          // Print all leaf nodes      print_Leaf(root->left);      print_Leaf(root->right);          // Print the right boundary in bottom-up manner      print_right_boundary(root->right);  }      // A function used to create a node  struct node* new_Node(int data)  {      struct node* temp = (struct node*)malloc(sizeof(struct node));          temp->data = data;      temp->left = temp->right = NULL;          return temp;  }      // main() function from where the execution gets started.  int main()  {      // first we construct a tree by calling the function new_Node()      struct node* root = new_Node(30);      root->left = new_Node(18);      root->left->left = new_Node(14);      root->left->right = new_Node(21);      root->left->right->left = new_Node(9);      root->left->right->right = new_Node(24);      root->right = new_Node(22);      root->right->right = new_Node(28);          print_boundary_nodes(root);          return 0;  }  

Output

Next TopicDiagonal Traversal of Binary Tree

Boundary Traversal of Binary tree

Boundary Traversal of Binary tree

Apriori Algorithm

DS Circular Queue

You may also like