Introduction
A binary tree is a generic tree with at most two children namely the left child and the right child. Here we are asked to do the boundary traversal of the binary tree but before that, we should understand what a boundary traversal is!
The boundary traversal of a binary tree implies that starting from the root node we have to print the boundary nodes in anticlockwise order. More specifically, we have to print:
- root node
- print the left boundary nodes
- print all leaf nodes
- print the right boundary nodes.
Let us understand it more clearly with the help of the below example:
Boundary traversal of the binary tree will be :
1 2 4 5 6 7 3
So, now we are clear with the term boundary traversal of the binary tree. Now is the time to move towards its solution.
Recommended: Try the Problem by yourself first before moving on to the solution
Must Recommended Topic, Binary Tree Postorder Traversal.
Recursive Approach For The Boundary Traversal Of Binary Tree.
To solve this problem we have to visualize the problem by breaking it into three steps:-
Step 1. The Left Boundary of the tree has to be printed in a top-down manner. We will be using recursion to print these.
Step 2. Leaf nodes have to be printed in the same manner as they got printed in the in-order traversal.
Step 3. The Right boundary nodes of the binary tree have to be printed in a bottom-up fashion. We can print them easily using recursion.
Following the above steps, you need to take care of a few edge cases.
- The root node is part of the left boundary as well as the right boundary. So we have to make sure that the root node gets printed only once in the output.
- Leaf nodes are part of the left boundary traversal and right boundary traversal. So we have to make sure that leaf nodes should not be printed twice. For this, we will skip leaf nodes while doing left and right boundary traversal.
C++ Code For the Boundary Traversal Of Binary Tree(Recursive)
#include<bits/stdc++.h>
using namespace std;
class node {
public:
//data members
int data;
node * left, * right;
//constructor
node() {
left = NULL;
right = NULL;
}
};
// print the leaves (nodes from the bottom)
void printLeaves(node * root) {
//base case
if (root == NULL)
return;
//given node is a leaf node
if ((root -> left) == NULL && (root -> right) == NULL)
cout << root -> data << " ";
//travelling recursively on left part
printLeaves(root -> left);
//travelling recursively on right part
printLeaves(root -> right);
}
// function for printing all the nodes of right boundary
void printLeft(node * root) {
//base case
if (root == NULL && (root -> left == NULL && root -> right == NULL))
return;
//if left child of root is present
if (root -> left != NULL) {
cout << root -> data << " ";
// recursively move down the left subtree
printLeft(root -> left);
} else if (root -> right != NULL) {
cout << root -> data << " ";
// recursively move down the right subtree
printLeft(root -> right);
}
}
// function for printing all the nodes of right boundary
void printRight(node * root) {
//base case
if (root == NULL || (root -> left == NULL && root -> right == NULL))
return;
//printing is done in bottom up manner
//if right child of root is present
if (root -> right != NULL) {
printRight(root -> right);
cout << root -> data << " ";
}
//if right child is not there then check for its left child
else if (root -> left != NULL) {
printRight(root -> left);
cout << root -> data << " ";
}
}
void boundaryTraversal(node * root) {
//If binary tree is NULL
if (root == NULL)
return;
//print the root node
cout << root -> data << " ";
//print the left boundary of binary tree
printLeft(root -> left);
//print the leaves of the left binary tree
printLeaves(root -> left);
//print the leaves of the right binary tree
printLeaves(root -> right);
//print the right boundary of binary tree
printRight(root -> right);
}
//function for the creation of a new node
node * createNode(int data) {
node * newNode = new node();
newNode -> data = data;
return newNode;
}
int main() {
//creating the binary tree
node * root = createNode(5);
root -> left = createNode(7);
root -> right = createNode(3);
root -> left -> left = createNode(9);
root -> left -> right = createNode(6);
root -> left -> right -> left = createNode(1);
root -> left -> right -> right = createNode(4);
// 5
// / \
// 7 3
// / \
// 9 6
// / \
// 1 4
//calling the function for boundary traversal
boundaryTraversal(root);
}
// Output:
// 5 7 9 1 4 3
Complexity Analysis
- Time Complexity: The time complexity of the above code will be O(N) where N will be the count of nodes in a binary tree. We are having linear time complexity as we have traversed each node of the binary tree.
- Space Complexity: The space complexity will be O(H) where H is the height of the binary tree. We have used recursion here for the left and right boundary traversal that’s why we need a call stack which is adding to the space complexity. In the case of skewed trees, the height of the tree can become N which gives a worst of O(N).
So, we are done with the boundary traversal of the binary tree.
But wait! I have one more way of writing this code. In an interview, you are expected to come up with all the approaches to a problem so here we are going to see the next approach as well.
The boundary traversal of a binary tree implies that starting from the root node we have to print the boundary nodes in anticlockwise order. For the implementation of code and conceptual knowledge watch this video.