Posted on by Kalkicode
Code Queue

Print Levels of all nodes in a Binary Tree

The given problem involves detecting and printing the levels of all nodes in a binary tree. The level of a node in a binary tree is defined as the distance from the root node to that node, where the root node is considered at level 1. The task is to create a Java program that traverses the binary tree using level-order traversal and prints the data of each node along with its corresponding level.

Problem Statement

The goal is to create a Java program that takes a binary tree as input and prints the data of each node in the tree along with its level (distance from the root node).

Explanation with Example

Consider the following binary tree:

Level indicating by node

Idea to Solve the Problem

To print the levels of all nodes in a binary tree, we will use a level-order traversal technique with the help of a custom queue data structure. During the level-order traversal, we will enqueue each node along with its corresponding level in the queue. Then, while dequeuing nodes from the queue, we will print the data of each node along with its level.

Pseudocode

  1. Create the TreeNode class to represent binary tree nodes with data, left, and right pointers.
  2. Create the QueueNode class to represent nodes of a custom queue, which stores TreeNode elements along with their levels.
  3. Implement the MyQueue class with methods to enqueue, dequeue, check if the queue is empty, etc.
  4. Create the BinaryTree class with methods to print the levels of all nodes in the tree (print_level).
  5. In the print_level() method:
    • Initialize a temporary node (node) to the root of the binary tree.
    • Create a new queue (MyQueue queue).
    • Enqueue the root node (node) along with level 1 into the queue.
    • While the queue is not empty, do the following:
      • Dequeue the current node along with its level from the front of the queue.
      • If the dequeued node has a left child, enqueue it into the queue along with its level+1.
      • If the dequeued node has a right child, enqueue it into the queue along with its level+1.
      • Print the data of the dequeued node along with its level.
  6. Create a binary tree and add nodes to it.
  7. Call the print_level() method on the binary tree to print the levels of all nodes.

Algorithm

The algorithm to print the levels of all nodes in a binary tree using level order traversal is as follows:

  1. Start from the root node of the binary tree.
  2. Enqueue the root node along with level 1 into the queue.
  3. While the queue is not empty:
    • Dequeue the current node along with its level from the front of the queue.
    • If the dequeued node has a left child, enqueue it into the queue along with its level+1.
    • If the dequeued node has a right child, enqueue it into the queue along with its level+1.
    • Print the data of the dequeued node along with its level.

Code Solution

Resultant Output Explanation

The program will print the data of each node in the binary tree along with its corresponding level. In the provided example, the binary tree looks like:


              10
             / \ 
            /   \
           2     3
          /     / \
         4     1   5
        /  \    \   \
       7    3    6  11
              \    /
               8  -3
              / \    
            -1   -2

The program will print the levels of all nodes in the tree as follows:


Node [10] is appear in level 1
Node [2] is appear in level 2
Node [3] is appear in level 2
Node [4] is appear in level 3
Node [1] is appear in level 3
Node [5] is appear in level 3
Node [7] is appear in level 4
Node [3] is appear in level 4
Node [6] is appear in level 4
Node [11] is appear in level 4
Node [8] is appear in level 5
Node [-3] is appear in level 5
Node [-1] is appear in level 6
Node [-2] is appear in level 6

Time Complexity

The time complexity of the print_level() method is O(N), where N is the number of nodes in the binary tree. This is because each node is visited once during the level-order traversal, and enqueueing and dequeueing operations on the queue take constant time. Overall, the time complexity of the entire program is O(N).

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment