Efficiently print all nodes between two given levels in a binary tree

Given a binary tree, efficiently print all nodes between two given levels in a binary tree. The nodes for any level should be printed from left to right.


 

For example, if starting level is 2 and ending level is 3, the solution should print nodes in following order – [2, 3, 4, 5, 6, 7]

 
Binary Tree

 
Simple solution would be to print all nodes of given levels one by one. All nodes present in a level can be printed by modifying pre-order traversal of the tree. The time complexity of above solution is O(n2).

 
We can reduce time complexity to O(n) by modifying Level order traversal. Below is the pseudocode for a modified level order traversal which maintains level of each node.

levelorder(root, start, end)
q -> empty queue
q.enqueue(root)
level -> 0
while (not q.isEmpty())
   size -> q.size()
   level = level + 1
   while(size)
      node -> q.dequeue()
      if (level between start and end)
         print(node)
      if (node.left <> null)
         q.enqueue(node.left)
      if (node.right <> null)
         q.enqueue(node.right)
      size = size - 1

 

 
Here’s a C++ program that demonstrates it:

 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 

 
We can also solve this problem by using Hashing. The idea is to traverse the tree in preorder fashion and store every node and its level into the multimap using level number as a key. Finally, we print all nodes corresponding to every level between given levels. Here’s a C++ implementation of it –

 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of