# Iterative diagonal traversal of binary tree

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

We have discussed recursive solution in below post.

Diagonal Traversal of Binary Tree

In this post, iterative solution is discussed. The idea is to use a queue to store only the left child of current node. After printing the data of current node make the current node to its right child, if present.
A delimiter NULL is used to mark the starting of next diagonal.

Below is the implementation of above approach.

## C++

 `/* C++ program to construct string from binary tree*/` `#include ` `using` `namespace` `std; ` ` `  `/* A binary tree node has data, pointer to left ` `   ``child and a pointer to right child */` `struct` `Node { ` `    ``int` `data; ` `    ``Node *left, *right; ` `}; ` ` `  `/* Helper function that allocates a new node */` `Node* newNode(``int` `data) ` `{ ` `    ``Node* node = (Node*)``malloc``(``sizeof``(Node)); ` `    ``node->data = data; ` `    ``node->left = node->right = NULL; ` `    ``return` `(node); ` `} ` ` `  `// Iterative function to print diagonal view ` `void` `diagonalPrint(Node* root) ` `{ ` `    ``// base case ` `    ``if` `(root == NULL) ` `        ``return``; ` ` `  `    ``// inbuilt queue of Treenode ` `    ``queue q; ` ` `  `    ``// push root ` `    ``q.push(root); ` ` `  `    ``// push delimiter ` `    ``q.push(NULL); ` ` `  `    ``while` `(!q.empty()) { ` `        ``Node* temp = q.front(); ` `        ``q.pop(); ` ` `  `        ``// if current is delimiter then insert another ` `        ``// for next diagonal and cout nextline ` `        ``if` `(temp == NULL) { ` ` `  `            ``// if queue is empty return ` `            ``if` `(q.empty()) ` `                ``return``; ` ` `  `            ``// output nextline ` `            ``cout << endl; ` ` `  `            ``// push delimiter again ` `            ``q.push(NULL); ` `        ``} ` `        ``else` `{ ` `            ``while` `(temp) { ` `                ``cout << temp->data << ``" "``; ` ` `  `                ``// if left child is present  ` `                ``// push into queue ` `                ``if` `(temp->left) ` `                    ``q.push(temp->left); ` ` `  `                ``// current equals to right child ` `                ``temp = temp->right; ` `            ``} ` `        ``} ` `    ``} ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``Node* root = newNode(8); ` `    ``root->left = newNode(3); ` `    ``root->right = newNode(10); ` `    ``root->left->left = newNode(1); ` `    ``root->left->right = newNode(6); ` `    ``root->right->right = newNode(14); ` `    ``root->right->right->left = newNode(13); ` `    ``root->left->right->left = newNode(4); ` `    ``root->left->right->right = newNode(7); ` `    ``diagonalPrint(root); ` `} `

## Java

 `// Java program to con string from binary tree ` `import` `java.util.*; ` `class` `solution ` `{ ` ` `  `   `  `// A binary tree node has data, pointer to left  ` ` ``//  child and a pointer to right child  ` `static` `class` `Node {  ` `    ``int` `data;  ` `    ``Node left, right;  ` `};  ` `   `  `// Helper function that allocates a new node  ` `static` `Node newNode(``int` `data)  ` `{  ` `    ``Node node = ``new` `Node();  ` `    ``node.data = data;  ` `    ``node.left = node.right = ``null``;  ` `    ``return` `(node);  ` `}  ` `   `  `// Iterative function to print diagonal view  ` `static` `void` `diagonalPrint(Node root)  ` `{  ` `    ``// base case  ` `    ``if` `(root == ``null``)  ` `        ``return``;  ` `   `  `    ``// inbuilt queue of Treenode  ` `    ``Queue q= ``new` `LinkedList();  ` `   `  `    ``// add root  ` `    ``q.add(root);  ` `   `  `    ``// add delimiter  ` `    ``q.add(``null``);  ` `   `  `    ``while` `(q.size()>``0``) {  ` `        ``Node temp = q.peek();  ` `        ``q.remove();  ` `   `  `        ``// if current is delimiter then insert another  ` `        ``// for next diagonal and cout nextline  ` `        ``if` `(temp == ``null``) {  ` `   `  `            ``// if queue is empty return  ` `            ``if` `(q.size()==``0``)  ` `                ``return``;  ` `   `  `            ``// output nextline  ` `            ``System.out.println(); ` `   `  `            ``// add delimiter again  ` `            ``q.add(``null``);  ` `        ``}  ` `        ``else` `{  ` `            ``while` `(temp!=``null``) {  ` `                ``System.out.print( temp.data + ``" "``);  ` `   `  `                ``// if left child is present   ` `                ``// add into queue  ` `                ``if` `(temp.left!=``null``)  ` `                    ``q.add(temp.left);  ` `   `  `                ``// current equals to right child  ` `                ``temp = temp.right;  ` `            ``}  ` `        ``}  ` `    ``}  ` `}  ` `   `  `// Driver Code  ` `public` `static` `void` `main(String args[]) ` `{  ` `    ``Node root = newNode(``8``);  ` `    ``root.left = newNode(``3``);  ` `    ``root.right = newNode(``10``);  ` `    ``root.left.left = newNode(``1``);  ` `    ``root.left.right = newNode(``6``);  ` `    ``root.right.right = newNode(``14``);  ` `    ``root.right.right.left = newNode(``13``);  ` `    ``root.left.right.left = newNode(``4``);  ` `    ``root.left.right.right = newNode(``7``);  ` `    ``diagonalPrint(root);  ` `}  ` `} ` `//contributed by Arnab Kundu `

## C#

 `// C# program to con string from binary tree ` `using` `System;  ` `using` `System.Collections; ` ` `  `class` `GFG ` `{ ` ` `  `// A binary tree node has data,  ` `// pointer to left child and ` `// a pointer to right child  ` `public` `class` `Node ` `{  ` `    ``public` `int` `data;  ` `    ``public` `Node left, right;  ` `};  ` `     `  `// Helper function that ` `// allocates a new node  ` `static` `Node newNode(``int` `data)  ` `{  ` `    ``Node node = ``new` `Node();  ` `    ``node.data = data;  ` `    ``node.left = node.right = ``null``;  ` `    ``return` `(node);  ` `}  ` `     `  `// Iterative function to print diagonal view  ` `static` `void` `diagonalPrint(Node root)  ` `{  ` `    ``// base case  ` `    ``if` `(root == ``null``)  ` `        ``return``;  ` `     `  `    ``// inbuilt queue of Treenode  ` `    ``Queue q = ``new` `Queue();  ` `     `  `    ``// Enqueue root  ` `    ``q.Enqueue(root);  ` `     `  `    ``// Enqueue delimiter  ` `    ``q.Enqueue(``null``);  ` `     `  `    ``while` `(q.Count > 0)  ` `    ``{  ` `        ``Node temp = (Node) q.Peek();  ` `        ``q.Dequeue();  ` `     `  `        ``// if current is delimiter then insert another  ` `        ``// for next diagonal and cout nextline  ` `        ``if` `(temp == ``null``)  ` `        ``{  ` `     `  `            ``// if queue is empty return  ` `            ``if` `(q.Count == 0)  ` `                ``return``;  ` `     `  `            ``// output nextline  ` `            ``Console.WriteLine(); ` `     `  `            ``// Enqueue delimiter again  ` `            ``q.Enqueue(``null``);  ` `        ``}  ` `        ``else`  `        ``{  ` `            ``while` `(temp != ``null``) ` `            ``{  ` `                ``Console.Write( temp.data + ``" "``);  ` `     `  `                ``// if left child is present  ` `                ``// Enqueue into queue  ` `                ``if` `(temp.left != ``null``)  ` `                    ``q.Enqueue(temp.left);  ` `     `  `                ``// current equals to right child  ` `                ``temp = temp.right;  ` `            ``}  ` `        ``}  ` `    ``}  ` `}  ` `     `  `// Driver Code  ` `public` `static` `void` `Main(String []args) ` `{  ` `    ``Node root = newNode(8);  ` `    ``root.left = newNode(3);  ` `    ``root.right = newNode(10);  ` `    ``root.left.left = newNode(1);  ` `    ``root.left.right = newNode(6);  ` `    ``root.right.right = newNode(14);  ` `    ``root.right.right.left = newNode(13);  ` `    ``root.left.right.left = newNode(4);  ` `    ``root.left.right.right = newNode(7);  ` `    ``diagonalPrint(root);  ` `}  ` `} ` ` `  `// This code is contributed by Arnab Kundu `

Output:

```8 10 14
3 6 7 13
1 4
```

## tags:

Tree cpp-queue Tree