Boundary Traversal Of Binary Tree (Recursive and Iterative)
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 3Complexity 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.
Iterative Boundary Traversal Of Binary Tree
In the last approach, we have discussed that there will be three steps for the boundary traversal of a binary tree. So the same thing applies here. Then you must be wondering what’s different in the second approach then!
So like the last approach, we have to break this problem down into three steps which are:
Step 1. The Left Boundary of the tree has to be printed in a top-down manner. In the last approach we used recursion for this but in this approach, we will be printing the left boundary with the help of a while loop i.e iteratively.
Step 2. The Right boundary nodes of the binary tree have to be printed in a bottom-up fashion. So here also we will be using a while loop instead of recursion to get the right boundary as output.
Step 3. We have to print the leaf nodes in a left-to-right manner. In the last approach, we achieved this using recursion. But now we are going to print them without recursion. But how?
So here goes the explanation:
We know that leaf nodes are found at the last level of a binary tree. So the task here is to print the last level of a binary tree in a left to right manner.
For printing the leaf nodes in a left to the right manner we have to make use of two stacks. Let’s see the steps:
Step 1: Take two stacks s1 and s2.
Step 2. In stack 1 we will be storing nodes that are not leaf nodes.
Step 3: In stack 2 we will be storing the nodes which are leaf nodes.
Step 4: Once stack 1 becomes empty we will be having all leaf nodes in our stack s2.
Step 5: Pop out the nodes from stack s2 and leaf nodes will be printed in a left to right manner.
Since we have understood the steps now is the time to code it. Let’s begin :
C++ Code For the Boundary Traversal Of Binary Tree(Iterative)
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
//data members
int data;
Node * left, * right;
//constructor
Node() {
left = NULL;
right = NULL;
}
};
void boundaryTraversal(Node * root) {
//checking if root is not NULL
if (root != NULL) {
//If a single node is there
if ((root -> left == NULL) && (root -> right == NULL)) {
cout << root -> data << endl;
return;
}
//This will store order of traversed nodes
vector < Node * > nodesOrder;
//pushing the node into this vector
nodesOrder.push_back(root);
//traversing the left boundary of binary tree
Node * L = root -> left;
//we are putting this condition as a check that we are not pushing leaf nodes in it.
while (L -> left) {
nodesOrder.push_back(L);
L = L -> left;
}
// printing leaf nodes iteratively
// Stack to store all the nodes of tree
stack < Node * > s1;
// Stack to store all the leaf nodes
stack < Node * > s2;
// Push the root node
s1.push(root);
while (!s1.empty()) {
Node * curr = s1.top();
s1.pop();
// If current node has a left child
// push it onto the first stack
if (curr -> left)
s1.push(curr -> left);
// If current node has a right child
// push it onto the first stack
if (curr -> right)
s1.push(curr -> right);
// If current node is a leaf node
// push it onto the second stack
else if (!curr -> left && !curr -> right)
s2.push(curr);
}
// Print all the leaf nodes
while (!s2.empty()) {
nodesOrder.push_back(s2.top());
s2.pop();
}
//traversing the right boundary of binary tree
vector < Node * > listRight;
Node * R = root -> right;
//we are putting this condition as a check that we are not pushing leaf nodes in it.
while (R -> right) {
listRight.push_back(R);
R = R -> right;
}
// Reversing the order of right traversal
reverse(listRight.begin(), listRight.end());
// Concatenating the two lists
nodesOrder.insert(nodesOrder.end(), listRight.begin(),
listRight.end());
// Printing the boundary traversal
for (auto i: nodesOrder) {
cout << i -> data << " ";
}
cout << endl;
return;
}
}
//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);
return 0;
}
// Output:
// 5 7 9 1 4 3Complexity 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(N) where N is the number of nodes in the binary tree. We are using two stacks for storing the nodes of a binary tree and hence the stack is adding to the space complexity.
Frequently Asked Questions
What is meant by a Binary tree?
A generic tree where each node can have two children at most is known as a binary tree.
Can I print the leaf nodes of the tree in boundary traversal without using a stack?
Yes, you can as we have discussed in method 1 of this blog. But this will cost you more in terms of time complexity as without a stack your time complexity will be O(N^2).
Can I use a queue instead of the stack to print the leaf nodes in the boundary traversal of a binary tree?
No! You have to use stack only because we want to get nodes we have entered first as the first output and it can only be achieved using the Last In First Out property of stack data structure.
Can I print the nodes in clockwise order in the boundary traversal of the binary tree?
No! You can’t. It’s mandatory to print nodes in the anticlockwise order in the boundary traversal of a binary tree.
Conclusion
In this blog, we have discussed two approaches i.e., recursive and iterative, for the boundary traversal of a binary tree. In the iterative approach, we used level order traversal to get leaf nodes printed in an anticlockwise manner. Try coding this out yourself now.
Recommended Problems:
Recommended Reading:
- Convert a Generic N-ary tree to a Binary Tree
- Diagonal Traversal of Binary Tree
- ZigZag Traversal of Binary Tree
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on CodeStudio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on CodeStudio.
Cheers!
Previous Article 
