# 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]

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:

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 –

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

(2 votes, average: 5.00 out of 5)