Boundary traversal of the Binary tree in C++

By Zeeshan Alam

In this tutorial, we will learn about how to find boundary traversal of the binary tree in C++.

We will also see some examples to understand the concept in a better way.

Boundary traversal of  binary tree

Boundary traversal of the binary tree is to traverse the boundary nodes of the tree in an anticlockwise direction.

Let’s see the diagram,

                           1
                        /    \
                      2         6
                      \      /    \
                       3   7        9  boundary traversal is 1-2-3-4-5-8-9-6.(anticlockwise)
                     /   \  \ 
                   4      5   8

So, in the above diagram, we can see the boundary traversal.

Let’s see the pseudocode,

printBoundary(root)
        1. if root==NULL return
        2. left(root->left)//traverse left boundary nodes
        3. leaf(root->left)//traverse left subtree leaf
        4. leaf(root->right)//traverse right subtree leaf
        5. right(root->right)//traverse right boundary nodes

So, in the above pseudocode, we can see the traversal in anticlockwise direction.

Here, we will see the code implementation for boundary traversal in c++.

Code implementation in C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct Node{
  int data;
  Node* left;
  Node* right;
};
//function to create node
Node* create(int x){
  Node* temp=(Node*)malloc(sizeof(Node));
  temp->data=x;
  temp->left=NULL;
  temp->right=NULL;
  return temp;
}
//function to move left subtree
void left(Node* root){
    if(root==NULL)return;
    if(root->left!=NULL){
        cout<<root->data<<" ";
        left(root->left);
    }
    else if(root->right!=NULL){
        cout<<root->data<<" ";
        left(root->right);
    }
}
//function to move right subtree
void right(Node* root){
    if(root==NULL)return;
    if(root->right!=NULL){
        right(root->right);
        cout<<root->data<<" ";
    }
    else if(root->left!=NULL){
        right(root->left);
        cout<<root->data<<" ";
    }
}
//function to move leaf node
void leaf(Node* root){
    if(root==NULL)return;
    if(root->left==NULL&&root->right==NULL)cout<<root->data<<" ";
    leaf(root->left);
    leaf(root->right);
}
//function for print boundary nodes
void printBoundary(Node *root)
{
     if(root==NULL)return;
     cout<<root->data<<" ";
     left(root->left);
     leaf(root->left);
     leaf(root->right);
     right(root->right);
     
}
//main function
int main(){
  Node* root=create(1);
  root->left=create(2);
  root->left->right=create(3);
  root->left->right->left=create(4);
  root->left->right->right=create(5);
  root->right=create(6);
  root->right->left=create(7);
  root->right->left->right=create(8);
  root->right->right=create(9);
  cout<<"Boundary traversal of the given binary tree is: "<<endl;
  printBoundary(root);
}

Output

Boundary traversal of the given binary tree is:
1 2 3 4 5 8 9 6

You may also learn,

Find out the Diameter of the Binary Tree in C++

Build Binary Tree in C++ (Competitive Programming)