## Sunday, May 8, 2016

### Diagonal Traversal of Binary Tree - GeeksforGeeks

Diagonal Traversal of Binary Tree - GeeksforGeeks
Consider lines of slope -1 passing between nodes. Given a Binary Tree, print all diagonal elements in a binary tree belonging to same line.

```Input : Root of below tree

Output :
Diagonal Traversal of binary tree :
8 10 14
3 6 7 13
1 4```
The idea is to use map. We use different slope distances and use them as key in map. Value in map is vector (or dynamic array) of nodes. We traverse the tree to store values in map. Once map is built, we print contents of it.

`oid` `diagonalPrintUtil(Node* root, ``int` `d,`
`                      ``map<``int``, vector<``int``>> &diagonalPrint)`
`{`
`    ``// Base case`
`    ``if` `(!root)`
`        ``return``;`

`    ``// Store all nodes of same line together as a vector`
`    ``diagonalPrint[d].push_back(root->data);`

`    ``// Increase the vertical distance if left child`
`    ``diagonalPrintUtil(root->left, d + 1, diagonalPrint);`

`    ``// Vertical distance remains same for right child`
`    ``diagonalPrintUtil(root->right, d, diagonalPrint);`
`}`

`// Print diagonal traversal of given binary tree`
`void` `diagonalPrint(Node* root)`
`{`
`    ``// create a map of vectors to store Diagonal elements`
`    ``map<``int``, vector<``int``> > diagonalPrint;`
`    ``diagonalPrintUtil(root, 0, diagonalPrint);`

`    ``cout << ``"Diagonal Traversal of binary tree : \n"``;`
`    ``for` `(``auto` `it = diagonalPrint.begin();`
`         ``it != diagonalPrint.end(); ++it)`
`    ``{`
`        ``for` `(``auto` `itr = it->second.begin();`
`             ``itr != it->second.end(); ++itr)`
`            ``cout << *itr  << ``' '``;`

`        ``cout << ``'\n'``;`
`    ``}`