Given a binary tree, print all nodes for each diagonal having negative slope (\). Assume that the left and right child of a node makes 45 degree angle with the parent.

The diagonals traversal is

1 3 6

2 5 8

4 7

This problem can be easily solved with the help of Hashing. The idea is to create an empty map where each key in the map represents a diagonal in the binary tree and its value maintains all nodes present in the diagonal. Then we do a pre-order traversal of the tree and update the map. For each node, we recurse for its left subtree by increasing diagonal by 1 and recurse for right subtree with same diagonal.

## C++

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 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Recursive function to do a pre-order traversal of the tree and // fill the map with diagonal elements void printDiagonal(Node *node, int diagonal, auto &map) { // base case: empty tree if (node == nullptr) return; // insert current node in current diagonal map.insert(make_pair(diagonal, node->data)); // recurse for left subtree by increasing diagonal by 1 printDiagonal(node->left, diagonal + 1, map); // recurse for right subtree with same diagonal printDiagonal(node->right, diagonal, map); } // Function to print the diagonal elements of given binary tree void printDiagonal(Node *root) { // create an empty map to store diagonal element in every slope // we can also use map<int, vector<int>> instead of multimap<int, int> multimap<int, int> map; // do pre-order traversal of the tree and fill the map printDiagonal(root, 0, map); // traverse the map and print diagonal elements int temp = 0; for (auto it = map.begin(); it != map.end(); it++) { if (temp != it->first) { cout << endl; temp = it->first; } cout << it->second << " "; } } |

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

##### Iterative version –

We can also use Queue to solve this problem. The idea is similar to level order traversal but instead of storing nodes of a level, we enqueue nodes in a diagonal.

## C++

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 |
// Iterative function to print the diagonal elements of given binary tree void diagonalPrint(Node* root) { // create an empty queue queue<Node*> q; // create a sentinel (dummy) node to denote end of a diagonal Node* sentinel = newNode(-1); // enqueue all nodes of first diagonal in binary tree while (root) { q.push(root); root = root->right; } // enqueue sentinel node at the end of each diagonal q.push(sentinel); // run till only sentinel is left while (q.size() != 1) { // dequeue front node Node* front = q.front(); q.pop(); if (front != sentinel) { // print current node cout << front->data << " "; // enqueue nodes of next diagonal in binary tree Node* node = front->left; while (node) { q.push(node); node = node->right; } } else { // if end of current diagonal is reached, enqueue sentinel node // and print newline q.push(sentinel); cout << endl; } } } |

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

**Exercise:**

Modify the solution to print diagonal elements for diagonals having positive slope (/).

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

Hi,

I think the time complexity of the recursive version is O(nlogn) as map has O(logn) complexity for each insertion/deletion/lookup. Please let me know if I’m wrong.

And also keep adding more algorithms. I find your code easy to understand, concise and up-to-date with c++14. Thanks!

Dibyendu, you’re right. Thanks for bringing this to our notice. We have update the complexity. And thanks for your feedback. Happy coding 🙂