Print Binary Tree Levels in Sorted Order

Approach

We can solve this problem by maintaining a set of all the nodes at the same level of the binary tree. This approach modifies the general approach of level order traversal of a binary tree using a queue to find out the answer to this coding problem. We will keep a separator that separates the nodes in different levels of the tree in the queue.

While popping out nodes from the queue, we will insert them in the set data structure. Whenever we encounter a separator, we will print the contents of the set and clear it.

Algorithm

1. Create a queue and push the root and a nullptr inside it.
2. Create an empty set.
3. While the queue is not empty, do the following:
4. Pop out a node from the queue.
5. If the node is a nullptr:
   1. If the set is empty, then break out of the while loop.
   2. Otherwise, print the contents of the set and clear it. Push nullptr into the queue.
6. Otherwise, insert node->val into the set and push its left and right child into the queue.

Implementation in C++

// Include the headers.
#include<bits/stdc++.h>
using namespace std;


// TreeNode definition.
struct TreeNode {
    int val;
    TreeNode* leftChild, *rightChild;
};


// Function to create a node of the tree.
TreeNode* createTreeNode(int val){
    TreeNode* node = new TreeNode();


    // Specify the data of the node and left and right pointers.
    node->val = val;
    node->leftChild = nullptr;
    node->rightChild = nullptr;


    // Return the node.
    return node;
}


// Function to print the sorted level order.
void sortedLevelOrder(TreeNode* root){
    // Create the queue and set.
    queue<TreeNode*> q;
    set<int> st;


    // Push the root and nullptr as discussed in the approach.
    q.push(root);
    q.push(nullptr);


    // Loop till the queue is not empty.
    while(!q.empty()){
        // Pop the node.
        TreeNode* node=q.front();
        q.pop();


        // If the node is nullptr, it means
        // a level of nodes has been popped out and is present in the set.
        if(node==nullptr){
            // If the set is empty, the tree traversal is complete.
            if(st.empty()) break;


            // Print the set contents.
            for(auto it:st){
                cout<<it<<" ";
            }
            cout<<endl;


            // Clear the set for the next level.
            st.clear();


            // Insert the separator for the current level.
            q.push(nullptr);
        }
        else{
            // Insert the current node's val.
            st.insert(node->val);


            // Push it's children.
            if(node->leftChild){
                q.push(node->leftChild);
            }
            if(node->rightChild){
                q.push(node->rightChild);
            }
        }
    }
}


int main()
{
    // Create the tree.
    TreeNode* root = createTreeNode(11);
    root->leftChild = createTreeNode(5);
    root->rightChild = createTreeNode(2);
    root->leftChild->leftChild = createTreeNode(10);
    root->leftChild->rightChild = createTreeNode(6);
    root->rightChild->leftChild = createTreeNode(7);
    root->rightChild->rightChild = createTreeNode(2);
    
    // Run the function solving the problem.
    sortedLevelOrder(root);   
    return 0;   
}

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

Run Code

Output

Time Complexity

The time complexity of the above approach is O(NlogN), where N is the number of nodes in the tree. It is because we are traversing the tree and inserting its elements into the set. The time complexity of insertion into a set is LogN where N is the size of the set.

Space Complexity

The space complexity of the approach is O(N), as we are storing the nodes in a queue. At any moment the size of the queue can be at most N/2.

Check out this problem - Connect Nodes At Same Level

Frequently Asked Questions

What is set in STL?

Set is a C++ STL container used to store the unique elements, and all the elements are stored in a sorted manner. Once the value is stored in the set, it cannot be modified within the set; instead, we can remove this value and can add the modified value of the element.

Which data structure is used in set STL?

Self-balancing Binary Search Tree (Mostly Red Black Tree)

Is Level order traversal the same as BFS?

Level Order traversal is also known as Breadth-First Traversal since it traverses all the nodes at each level before going to the next level (depth). The last level of the tree is always equal to the height of the tree.

Conclusion

In this blog, we discussed a coding problem involving a tricky modification of Level Order Traversal of a tree. We modified the technique and introduced the concept of set data structure to solve the problem. We discussed the time and space complexity of the approach as well.

Cheers, you have reached the end. Hope you liked the blog and it has added some knowledge to your life. Please have a look at these similar problems to learn more: Level Order Traversal, Specific LOT, Reverse Level Order Traversal, Disjoint-set data structure.

Refer to our Coding Ninjas Studio Guided Path to learn Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and even more! If you want to put your coding skills to the test, check out the mock test series and participate in the contests hosted by Coding Ninjas Studio! But say you're just starting out and want to learn about questions posed by tech titans like Amazon, Microsoft, Uber, and so on. In such a case, for placement preparations, you can also look at the problems, interview experiences, and interview bundle.

You should also consider our premium courses to offer your career an advantage over others!

Please upvote our blogs if you find them useful and interesting!

Happy Studying!