Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
What is a binary tree?
3.2.
What is level order traversal in a binary tree?
3.3.
What is the level in a binary tree?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Print Levels of all Nodes in a Binary Tree

Author Harsh
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

One of the most vital topics to know if you want to get a job at a top product-based organization is data structure and algorithms. Having a thorough understanding of DSA requires the solutions of various coding problems. So, in this blog, we will discuss a coding problem where we have to print the level of all nodes in a binary tree. We will be using a queue data structure to solve the problem.

Problem Statement

Given a binary tree, You have to print levels of all nodes in a binary tree. The level of a tree is explained in the image below:

Sample Examples

Input

Output

Node 2, Level: 1
Node 1, Level: 2
Node 5, Level: 2
Node 7, Level: 3
Node 9, Level: 3

 

Explanation

 

Example 2

Input

Output

Node 5, Level: 1
Node 9, Level: 2
Node 6, Level: 2
Node 7, Level: 3
Node 2, Level: 3

 

Explanation

Approach

We’ll create a queue to store the node and its level. Then we’ll do a level order traversal in which we’ll first print the level of the first element from the queue and then we’ll push the left and right children of that node into our queue. We'll keep on repeating this process until our queue becomes empty.

Algorithm

  1. Create a queue to store the tree node with level.
  2. Push the root node into the queue with 1 as the level.
  3. Do a level order traversal
    1. Get the first element from the queue and print its level.
    2. Push the left and right child of the node into the queue.
    3. Keep repeating the above steps until our queue becomes empty.
  4. Exit

Implementation in C++

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

// our node
class Node
{
public:
    int data;
    Node *left;
    Node *right;

    Node(int data)
    {
        this->data = data;
        left = nullptr;
        right = nullptr;
    }
};

void print_level(Node *root)
{
    // if root node is null
    // return
    if (!root)
        return;

    // queue for storing tree node with level
    queue<pair<Node *, int>> q;

    // pushing root node
    q.push({root, 1});

    // storing node with level
    pair<Node *, int> p;

    // level order traversal
    while (!q.empty())
    {
        p = q.front();
        q.pop();

        // printing the level of node
        cout << "Node " << p.first->data << ", Level: " << p.second << "\n";

        if (p.first->left)
            q.push({p.first->left, p.second + 1});
        if (p.first->right)
            q.push({p.first->right, p.second + 1});
    }
}

// main function
int main()
{
    // root node
    Node *root = NULL;

    // Constructing binary tree
    root = new Node(2);
    root->left = new Node(1);
    root->right = new Node(5);
    root->right->left = new Node(7);
    root->right->right = new Node(9);

    // calling the function
    print_level(root);

    return 0;
}

 

Output

Node 2, Level: 1
Node 1, Level: 2
Node 5, Level: 2
Node 7, Level: 3
Node 9, Level: 3

Time Complexity

Time complexity is O(n), where n is the number of nodes in a binary tree.

Space Complexity

A queue is used to store the node with its level. So, the space complexity of our program is O(n).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a binary tree?

It is a type of tree where each node can have a maximum of two children. Because the binary term implies 'two,' each node can have either zero, one, or two children.
 

What is level order traversal in a binary tree?

We visit all the nodes of a previous level before going on to the next level in level order traversal. Because we cover the breadth of a tree first in level order traversal, it's also known as the Breadth-First search.
 

What is the level in a binary tree?

The root node is the topmost node in a binary tree. The number of edges along the unique path between a node and the root node determines its level.

Conclusion

In this article, we have extensively discussed a coding problem where we have to print the level of all nodes in a binary tree.

We hope that this blog has helped you enhance your knowledge about the above question and if you would like to learn more, check out our articles Level Order Traversal Of  A Binary TreePrint the node values at odd levels of a Binary treeReplace each node in a binary tree with the sum of its inorder predecessor and successor, and many more on our Website.


Recommended Problems:

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Happy Learning!

Live masterclass