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(n^{2}).

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.

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

**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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Iterative function to print all nodes between two given // levels in a binary tree void printNodes(Node *root, int start, int end) { if (root == nullptr) return; // create an empty queue and enqueue root node list<Node*> queue; queue.push_back(root); // pointer to store current node Node* curr = nullptr; // maintains level of current node int level = 0; // run till queue is not empty while (!queue.empty()) { // increment level by 1 level++; // calculate number of nodes in current level int size = queue.size(); // process every node of current level and enqueue their // non-empty left and right child to queue while (size--) { curr = queue.front(); queue.pop_front(); // print the node if its level is between given levels if (level >= start && level <= end) cout << curr->key << " "; if (curr->left) queue.push_back(curr->left); if (curr->right) queue.push_back(curr->right); } if (level >= start && level <= end) cout << endl; } } |

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 –

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // traverse the tree in pre-order fashion and store nodes into the map // corresponding to their level void printNodes(Node *root, int start, int end, int level, auto &map) { // base case: empty tree if (root == nullptr) return; // push current node into the map corresponding to their level if (level >= start && level <= end) map[level].push_back(root->key); // recurse for left and right subtree by increasing level by 1 printNodes(root->left, start, end, level + 1, map); printNodes(root->right, start, end, level + 1, map); } // Recursive function to print all nodes between two given // levels in a binary tree void printNodes(Node *root, int start, int end) { // create an empty map to store nodes between given levels map<int, vector<int>> map; // traverse the tree and insert its nodes into the map // corresponding to the their level printNodes(root, start, end, 1, map); // iterate through the map and print all nodes between given levels for (auto it: map) { cout << "Level " << it.first << ": "; for (int i: it.second) cout << i << " "; cout << endl; } } |

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