Given a binary tree, print corner nodes of every level in it.

For example, consider below tree

**Output:**

6

3 8

4 2

1 3

The idea is very simple. We modify level order traversal of binary tree to maintain level of each node. Then, while doing level order traversal, if the current node happens to be the first node or last node in current level, we simply print it.

**C++ implementation –**

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 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Iterative function to print corner nodes of every level in binary tree void print(Node *root) { // return if tree is empty if (root == nullptr) return; // create an empty queue to store Tree nodes queue<Node*> q; // enqueue root node q.push(root); // run till queue is not empty while (!q.empty()) { // get size of current level int size = q.size(); int n = size; // process all nodes present in current level while (n--) { Node *node = q.front(); q.pop(); // if corner node found, print it if (n == size - 1 || n == 0) cout << node->data << " "; // enqueue left and right child of current node if (node->left != nullptr) q.push(node->left); if (node->right != nullptr) q.push(node->right); } // terminate the level by printing newline 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 our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply