Given a binary tree, assume that the left and right child of a node makes a 45 degree angle with the parent.

Print all diagonal elements in the binary tree that belong to the same line, see the example below for illustration:

##### Example 1: Print diagonal traversal of a binary tree

Input:

**Output: **

1,3,6 2,5,8,9 4,7

## Solutions

### Method 1: Using Map (Recursion)

We can perform **diagonal traversal** on a binary tree using a **Map**, the idea is to group the nodes diagonally and print the map in ascending order of "diagional-number (key)".

Each key in the map represents a diagonal in the binary tree, and its value maintains all nodes present in the diagonal.

Do a level-order traversal and **pass current-diagonal-number**, "0" for the root; right child will have same number while the left child will get "+1" of his parent.

##### Complexity

**O(n)**and space complexity is

**O(n)**due to auxiliary Map.

### Method 2: Using Queue

We can perform **diagonal traversal** on a binary tree using a **Queue**, the idea is to keep on printing right child and pushing left child to the queue.

Only when the element's left is available will we push it into the queue.

We'll process the node and then go to the right.

##### Complexity

**O(n)**and space complexity is

**O(n)**due to auxiliary Queue.