Boundary Traversal Of Binary Tree (Recursive and Iterative)

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

You can also try this code with Online C++ Compiler

Run Code

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 to the space complexity.

Must Read Recursion in Data Structure

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:

• Boundary Traversal Of Binary Tree
• Burn Tree
• Size of largest BST in a Binary Tree.
• Partial BST
• Zig Zag Tree Traversal 
• Preorder Traversal
   

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 Coding Ninjas Studio.

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 Coding Ninjas Studio.

Cheers!