Boundary traversal of the Binary tree in C++
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,
Leave a Reply