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:

  1. root node
  2. print the left boundary nodes
  3. print all leaf nodes
  4. print the right boundary nodes.

 

Let us understand it more clearly with the help of the below example:

 

Boundary traversal of 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.

Recursive Approach For The Boundary Traversal Of Binary Tree.

To solve this problem we have to visualize this 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 inorder 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.

  1. The root node is the 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.
  2. 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 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 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(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 into the space complexity.

Frequently Asked Questions

Ques 1. What is meant by a Binary tree? 
Ans1. A generic tree where each node can have two children at most is known as a binary tree.


Ques 2. Can I print the leaf nodes of the tree in boundary traversal without using a stack?
Ans 2. 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).


Ques 3. Can I use a queue instead of the stack to print the leaf nodes in the boundary traversal of a binary tree?
Ans 3. No! You have to use stack only because we want to get nodes we have entered first as first output and it can only be achieved using the Last In First Out property of stack data structure.

 

Ques 4. Can I print the nodes in clockwise order in the boundary traversal of binary tree?
Ans 4. No! You can’t. It’s mandatory to print nodes in the anticlockwise order in the boundary traversal of binary tree.

Key takeaways:

In this blog, we have discussed two approaches i.e., recursive and iterative, for the boundary traversal of 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. I hope this blog has helped you in adding some value to your knowledge. Do share it on social media and help us spread this knowledge. Happy Coding :)

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think