# Iterative diagonal traversal of binary tree

Here given code implementation process.

``````/*
Java program
Iterative diagonal traversal of binary tree
*/
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class QNode
{
public TreeNode data;
public QNode next;
public QNode(TreeNode data)
{
this.data = data;
this.next = null;
}
}
// Define custom queue class
class MyQueue
{
public QNode front;
public QNode rear;
public int size;
public MyQueue()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
public void enqueue(TreeNode data)
{
QNode node = new QNode(data);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size++;
this.rear = node;
}
// Delete front node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size--;
}
}
public int isSize()
{
return this.size;
}
public boolean isEmpty()
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
public QNode peek()
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front;
}
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
public void diagonalTraversal()
{
if (this.root == null)
{
System.out.print("Empty Tree\n");
return;
}
int count = 0;
TreeNode temp = null;
// Empty Queue
MyQueue record = new MyQueue();
// Use to managing a new line
int[] track = new int[2];
track[0] = 0;
track[1] = 0;
record.enqueue(this.root);
while (record.isEmpty() == false)
{
// Collect Tree node
temp = record.peek().data;
while (temp != null)
{
System.out.print("  " + (temp.data));
if (temp.left != null)
{
count++;
record.enqueue(temp.left);
}
// Visit to right child
temp = temp.right;
}
// Logic to include new line
if (track[0] == 0)
{
// Include new line
System.out.print("\n");
track[1] += count;
track[0] = track[1] - 1;
track[1] = 0;
}
else
{
track[0] -= 1;
track[1] += count;
}
count = 0;
// Remove front node
record.dequeue();
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
1
/   \
2     3
/ \   / \
3   4 6   5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       4
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(-2);
tree.root.right.left.right.right.right = new TreeNode(12);
tree.root.right.left.right.left.left = new TreeNode(-5);
tree.root.right.left.right.left.left.left = new TreeNode(6);
tree.root.right.left.right.right.right.left = new TreeNode(-4);
// Test
tree.diagonalTraversal();
}
}``````

#### Output

``````  1  3  5  2
2  4  6  4  -2  12
3  -7  1  -4
9  -5
6``````
``````// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Iterative diagonal traversal of binary tree
*/
// Binary Tree node
class TreeNode
{
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class QNode
{
public:
TreeNode *data;
QNode *next;
QNode(TreeNode *data)
{
this->data = data;
this->next = NULL;
}
};
// Define custom queue class
class MyQueue
{
public:
QNode *front;
QNode *rear;
int size;
MyQueue()
{
this->front = NULL;
this->rear = NULL;
this->size = 0;
}
// Add a new node at last of queue
void enqueue(TreeNode *data)
{
QNode *node = new QNode(data);
if (this->front == NULL)
{
// When first node of queue
this->front = node;
}
else
{
// Add node at last level
this->rear->next = node;
}
this->size++;
this->rear = node;
}
// Delete front node of queue
void dequeue()
{
if (this->front != NULL)
{
if (this->rear == this->front)
{
this->rear = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
}
this->size--;
}
}
int isSize()
{
return this->size;
}
bool isEmpty()
{
if (this->isSize() == 0)
{
return true;
}
return false;
}
QNode *peek()
{
if (this->isSize() == 0)
{
return NULL;
}
else
{
return this->front;
}
}
};
class BinaryTree
{
public:
TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
void diagonalTraversal()
{
if (this->root == NULL)
{
cout << "Empty Tree\n";
return;
}
int count = 0;
TreeNode *temp = NULL;
// Empty Queue
MyQueue *record = new MyQueue();
// Use to managing a new line
int track[2];
track[0] = 0;
track[1] = 0;
record->enqueue(this->root);
while (record->isEmpty() == false)
{
// Collect Tree node
temp = record->peek()->data;
while (temp != NULL)
{
cout << "  " << (temp->data);
if (temp->left != NULL)
{
count++;
record->enqueue(temp->left);
}
// Visit to right child
temp = temp->right;
}
// Logic to include new line
if (track[0] == 0)
{
// Include new line
cout << "\n";
track[1] += count;
track[0] = track[1] - 1;
track[1] = 0;
}
else
{
track[0] -= 1;
track[1] += count;
}
count = 0;
// Remove front node
record->dequeue();
}
}
};
int main()
{
BinaryTree *tree = new BinaryTree();
/*
1
/   \
2     3
/ \   / \
3   4 6   5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       4
-----------------------
Binary Tree
-----------------------
*/
tree->root = new TreeNode(1);
tree->root->left = new TreeNode(2);
tree->root->right = new TreeNode(3);
tree->root->left->left = new TreeNode(3);
tree->root->left->right = new TreeNode(4);
tree->root->left->right->left = new TreeNode(-7);
tree->root->left->right->left->left = new TreeNode(9);
tree->root->right->left = new TreeNode(6);
tree->root->right->right = new TreeNode(5);
tree->root->right->left->right = new TreeNode(4);
tree->root->right->right->right = new TreeNode(2);
tree->root->right->left->right->left = new TreeNode(1);
tree->root->right->left->right->right = new TreeNode(-2);
tree->root->right->left->right->right->right = new TreeNode(12);
tree->root->right->left->right->left->left = new TreeNode(-5);
tree->root->right->left->right->left->left->left = new TreeNode(6);
tree->root->right->left->right->right->right->left = new TreeNode(-4);
// Test
tree->diagonalTraversal();
return 0;
}``````

#### Output

``````  1  3  5  2
2  4  6  4  -2  12
3  -7  1  -4
9  -5
6``````
``````// Include namespace system
using System;
/*
Csharp program
Iterative diagonal traversal of binary tree
*/
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class QNode
{
public TreeNode data;
public QNode next;
public QNode(TreeNode data)
{
this.data = data;
this.next = null;
}
}
// Define custom queue class
public class MyQueue
{
public QNode front;
public QNode rear;
public int size;
public MyQueue()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
public void enqueue(TreeNode data)
{
QNode node = new QNode(data);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size++;
this.rear = node;
}
// Delete front node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size--;
}
}
public int isSize()
{
return this.size;
}
public Boolean isEmpty()
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
public QNode peek()
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front;
}
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
public void diagonalTraversal()
{
if (this.root == null)
{
Console.Write("Empty Tree\n");
return;
}
int count = 0;
TreeNode temp = null;
// Empty Queue
MyQueue record = new MyQueue();
// Use to managing a new line
int[] track = new int[2];
track[0] = 0;
track[1] = 0;
record.enqueue(this.root);
while (record.isEmpty() == false)
{
// Collect Tree node
temp = record.peek().data;
while (temp != null)
{
Console.Write("  " + (temp.data));
if (temp.left != null)
{
count++;
record.enqueue(temp.left);
}
// Visit to right child
temp = temp.right;
}
// Logic to include new line
if (track[0] == 0)
{
// Include new line
Console.Write("\n");
track[1] += count;
track[0] = track[1] - 1;
track[1] = 0;
}
else
{
track[0] -= 1;
track[1] += count;
}
count = 0;
// Remove front node
record.dequeue();
}
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
1
/   \
2     3
/ \   / \
3   4 6   5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       4
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(-2);
tree.root.right.left.right.right.right = new TreeNode(12);
tree.root.right.left.right.left.left = new TreeNode(-5);
tree.root.right.left.right.left.left.left = new TreeNode(6);
tree.root.right.left.right.right.right.left = new TreeNode(-4);
// Test
tree.diagonalTraversal();
}
}``````

#### Output

``````  1  3  5  2
2  4  6  4  -2  12
3  -7  1  -4
9  -5
6``````
``````package main
import "fmt"
/*
Go program
Iterative diagonal traversal of binary tree
*/
// Binary Tree node
type TreeNode struct {
data int
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
// Set node value
me.data = data
me.left = nil
me.right = nil
return me
}
type QNode struct {
data * TreeNode
next * QNode
}
func getQNode(data * TreeNode) * QNode {
var me *QNode = &QNode {}
me.data = data
me.next = nil
return me
}
// Define custom queue class
type MyQueue struct {
front * QNode
rear * QNode
size int
}
func getMyQueue() * MyQueue {
var me *MyQueue = &MyQueue {}
me.front = nil
me.rear = nil
me.size = 0
return me
}
// Add a new node at last of queue
func(this *MyQueue) enqueue(data * TreeNode) {
var node * QNode = getQNode(data)
if this.front == nil {
// When first node of queue
this.front = node
} else {
// Add node at last level
this.rear.next = node
}
this.size++
this.rear = node
}
// Delete front node of queue
func(this *MyQueue) dequeue() {
if this.front != nil {
if this.rear == this.front {
this.rear = nil
this.front = nil
} else {
this.front = this.front.next
}
this.size--
}
}
func(this MyQueue) isSize() int {
return this.size
}
func(this MyQueue) isEmpty() bool {
if this.isSize() == 0 {
return true
}
return false
}
func(this MyQueue) peek() * QNode {
if this.isSize() == 0 {
return nil
} else {
return this.front
}
}
type BinaryTree struct {
root * TreeNode
}
func getBinaryTree() * BinaryTree {
var me *BinaryTree = &BinaryTree {}
// Set initial value
me.root = nil
return me
}
func(this BinaryTree) diagonalTraversal() {
if this.root == nil {
fmt.Print("Empty Tree\n")
return
}
var count int = 0
var temp * TreeNode = nil
// Empty Queue
var record * MyQueue = getMyQueue()
// Use to managing a new line
var track = make([] int, 2)
record.enqueue(this.root)
for (record.isEmpty() == false) {
// Collect Tree node
temp = record.peek().data
for (temp != nil) {
fmt.Print("  ", (temp.data))
if temp.left != nil {
count++
record.enqueue(temp.left)
}
// Visit to right child
temp = temp.right
}
// Logic to include new line
if track[0] == 0 {
// Include new line
fmt.Print("\n")
track[1] += count
track[0] = track[1] - 1
track[1] = 0
} else {
track[0] -= 1
track[1] += count
}
count = 0
// Remove front node
record.dequeue()
}
}
func main() {
var tree * BinaryTree = getBinaryTree()
/*
1
/   \
2     3
/ \   / \
3   4 6   5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       4
-----------------------
Binary Tree
-----------------------
*/
tree.root = getTreeNode(1)
tree.root.left = getTreeNode(2)
tree.root.right = getTreeNode(3)
tree.root.left.left = getTreeNode(3)
tree.root.left.right = getTreeNode(4)
tree.root.left.right.left = getTreeNode(-7)
tree.root.left.right.left.left = getTreeNode(9)
tree.root.right.left = getTreeNode(6)
tree.root.right.right = getTreeNode(5)
tree.root.right.left.right = getTreeNode(4)
tree.root.right.right.right = getTreeNode(2)
tree.root.right.left.right.left = getTreeNode(1)
tree.root.right.left.right.right = getTreeNode(-2)
tree.root.right.left.right.right.right = getTreeNode(12)
tree.root.right.left.right.left.left = getTreeNode(-5)
tree.root.right.left.right.left.left.left = getTreeNode(6)
tree.root.right.left.right.right.right.left = getTreeNode(-4)
// Test
tree.diagonalTraversal()
}``````

#### Output

``````  1  3  5  2
2  4  6  4  -2  12
3  -7  1  -4
9  -5
6``````
``````<?php
/*
Php program
Iterative diagonal traversal of binary tree
*/
// Binary Tree node
class TreeNode
{
public \$data;
public \$left;
public \$right;
public	function __construct(\$data)
{
// Set node value
\$this->data = \$data;
\$this->left = NULL;
\$this->right = NULL;
}
}
class QNode
{
public \$data;
public \$next;
public	function __construct(\$data)
{
\$this->data = \$data;
\$this->next = NULL;
}
}
// Define custom queue class
class MyQueue
{
public \$front;
public \$rear;
public \$size;
public	function __construct()
{
\$this->front = NULL;
\$this->rear = NULL;
\$this->size = 0;
}
// Add a new node at last of queue
public	function enqueue(\$data)
{
\$node = new QNode(\$data);
if (\$this->front == NULL)
{
// When first node of queue
\$this->front = \$node;
}
else
{
// Add node at last level
\$this->rear->next = \$node;
}
\$this->size++;
\$this->rear = \$node;
}
// Delete front node of queue
public	function dequeue()
{
if (\$this->front != NULL)
{
if (\$this->rear == \$this->front)
{
\$this->rear = NULL;
\$this->front = NULL;
}
else
{
\$this->front = \$this->front->next;
}
\$this->size--;
}
}
public	function isSize()
{
return \$this->size;
}
public	function isEmpty()
{
if (\$this->isSize() == 0)
{
return true;
}
return false;
}
public	function peek()
{
if (\$this->isSize() == 0)
{
return NULL;
}
else
{
return \$this->front;
}
}
}
class BinaryTree
{
public \$root;
public	function __construct()
{
\$this->root = NULL;
}
public	function diagonalTraversal()
{
if (\$this->root == NULL)
{
echo("Empty Tree\n");
return;
}
\$count = 0;
\$temp = NULL;
// Empty Queue
\$record = new MyQueue();
// Use to managing a new line
\$track = array_fill(0, 2, 0);
\$track[0] = 0;
\$track[1] = 0;
\$record->enqueue(\$this->root);
while (\$record->isEmpty() == false)
{
// Collect Tree node
\$temp = \$record->peek()->data;
while (\$temp != NULL)
{
echo("  ".(\$temp->data));
if (\$temp->left != NULL)
{
\$count++;
\$record->enqueue(\$temp->left);
}
// Visit to right child
\$temp = \$temp->right;
}
// Logic to include new line
if (\$track[0] == 0)
{
// Include new line
echo("\n");
\$track[1] += \$count;
\$track[0] = \$track[1] - 1;
\$track[1] = 0;
}
else
{
\$track[0] -= 1;
\$track[1] += \$count;
}
\$count = 0;
// Remove front node
\$record->dequeue();
}
}
}

function main()
{
\$tree = new BinaryTree();
/*
1
/   \
2     3
/ \   / \
3   4 6   5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       4
-----------------------
Binary Tree
-----------------------
*/
\$tree->root = new TreeNode(1);
\$tree->root->left = new TreeNode(2);
\$tree->root->right = new TreeNode(3);
\$tree->root->left->left = new TreeNode(3);
\$tree->root->left->right = new TreeNode(4);
\$tree->root->left->right->left = new TreeNode(-7);
\$tree->root->left->right->left->left = new TreeNode(9);
\$tree->root->right->left = new TreeNode(6);
\$tree->root->right->right = new TreeNode(5);
\$tree->root->right->left->right = new TreeNode(4);
\$tree->root->right->right->right = new TreeNode(2);
\$tree->root->right->left->right->left = new TreeNode(1);
\$tree->root->right->left->right->right = new TreeNode(-2);
\$tree->root->right->left->right->right->right = new TreeNode(12);
\$tree->root->right->left->right->left->left = new TreeNode(-5);
\$tree->root->right->left->right->left->left->left = new TreeNode(6);
\$tree->root->right->left->right->right->right->left = new TreeNode(-4);
// Test
\$tree->diagonalTraversal();
}
main();``````

#### Output

``````  1  3  5  2
2  4  6  4  -2  12
3  -7  1  -4
9  -5
6``````
``````/*
Node JS program
Iterative diagonal traversal of binary tree
*/
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class QNode
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
// Define custom queue class
class MyQueue
{
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
enqueue(data)
{
var node = new QNode(data);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size++;
this.rear = node;
}
// Delete front node of queue
dequeue()
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size--;
}
}
isSize()
{
return this.size;
}
isEmpty()
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
peek()
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front;
}
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
diagonalTraversal()
{
if (this.root == null)
{
process.stdout.write("Empty Tree\n");
return;
}
var count = 0;
var temp = null;
// Empty Queue
var record = new MyQueue();
// Use to managing a new line
var track = Array(2).fill(0);
track[0] = 0;
track[1] = 0;
record.enqueue(this.root);
while (record.isEmpty() == false)
{
// Collect Tree node
temp = record.peek().data;
while (temp != null)
{
process.stdout.write("  " + (temp.data));
if (temp.left != null)
{
count++;
record.enqueue(temp.left);
}
// Visit to right child
temp = temp.right;
}
// Logic to include new line
if (track[0] == 0)
{
// Include new line
process.stdout.write("\n");
track[1] += count;
track[0] = track[1] - 1;
track[1] = 0;
}
else
{
track[0] -= 1;
track[1] += count;
}
count = 0;
// Remove front node
record.dequeue();
}
}
}

function main()
{
var tree = new BinaryTree();
/*
1
/   \
2     3
/ \   / \
3   4 6   5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       4
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(-2);
tree.root.right.left.right.right.right = new TreeNode(12);
tree.root.right.left.right.left.left = new TreeNode(-5);
tree.root.right.left.right.left.left.left = new TreeNode(6);
tree.root.right.left.right.right.right.left = new TreeNode(-4);
// Test
tree.diagonalTraversal();
}
main();``````

#### Output

``````  1  3  5  2
2  4  6  4  -2  12
3  -7  1  -4
9  -5
6``````
``````#    Python 3 program
#    Iterative diagonal traversal of binary tree

#  Binary Tree node
class TreeNode :
def __init__(self, data) :
#  Set node value
self.data = data
self.left = None
self.right = None

class QNode :
def __init__(self, data) :
self.data = data
self.next = None

#  Define custom queue class
class MyQueue :
def __init__(self) :
self.front = None
self.rear = None
self.size = 0

#  Add a new node at last of queue
def enqueue(self, data) :
node = QNode(data)
if (self.front == None) :
#  When first node of queue
self.front = node
else :
#  Add node at last level
self.rear.next = node

self.size += 1
self.rear = node

#  Delete front node of queue
def dequeue(self) :
if (self.front != None) :
if (self.rear == self.front) :
self.rear = None
self.front = None
else :
self.front = self.front.next

self.size -= 1

def isSize(self) :
return self.size

def isEmpty(self) :
if (self.isSize() == 0) :
return True

return False

def peek(self) :
if (self.isSize() == 0) :
return None
else :
return self.front

class BinaryTree :
def __init__(self) :
self.root = None

def diagonalTraversal(self) :
if (self.root == None) :
print("Empty Tree")
return

count = 0
temp = None
#  Empty Queue
record = MyQueue()
#  Use to managing a new line
track = [0] * (2)
track[0] = 0
track[1] = 0
record.enqueue(self.root)
while (record.isEmpty() == False) :
#  Collect Tree node
temp = record.peek().data
while (temp != None) :
print("  ", (temp.data), end = "")
if (temp.left != None) :
count += 1
record.enqueue(temp.left)

#  Visit to right child
temp = temp.right

#  Logic to include new line
if (track[0] == 0) :
#  Include new line
print(end = "\n")
track[1] += count
track[0] = track[1] - 1
track[1] = 0
else :
track[0] -= 1
track[1] += count

count = 0
#  Remove front node
record.dequeue()

def main() :
tree = BinaryTree()
#         1
#       /   \
#      2     3
#     / \   / \
#    3   4 6   5
#       /   \   \
#     -7     4   2
#     /     / \
#    9     1  -2
#         /     \
#       -5       12
#       /       /
#      6       4
# -----------------------
#    Binary Tree
# -----------------------
tree.root = TreeNode(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.left.left = TreeNode(3)
tree.root.left.right = TreeNode(4)
tree.root.left.right.left = TreeNode(-7)
tree.root.left.right.left.left = TreeNode(9)
tree.root.right.left = TreeNode(6)
tree.root.right.right = TreeNode(5)
tree.root.right.left.right = TreeNode(4)
tree.root.right.right.right = TreeNode(2)
tree.root.right.left.right.left = TreeNode(1)
tree.root.right.left.right.right = TreeNode(-2)
tree.root.right.left.right.right.right = TreeNode(12)
tree.root.right.left.right.left.left = TreeNode(-5)
tree.root.right.left.right.left.left.left = TreeNode(6)
tree.root.right.left.right.right.right.left = TreeNode(-4)
#  Test
tree.diagonalTraversal()

if __name__ == "__main__": main()``````

#### Output

``````   1   3   5   2
2   4   6   4   -2   12
3   -7   1   -4
9   -5
6``````
``````#    Ruby program
#    Iterative diagonal traversal of binary tree

#  Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :data, :left, :right
def initialize(data)
#  Set node value
self.data = data
self.left = nil
self.right = nil
end

end

class QNode
# Define the accessor and reader of class QNode
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end

end

#  Define custom queue class
class MyQueue
# Define the accessor and reader of class MyQueue
attr_accessor :front, :rear, :size
def initialize()
self.front = nil
self.rear = nil
self.size = 0
end

#  Add a new node at last of queue
def enqueue(data)
node = QNode.new(data)
if (self.front == nil)
#  When first node of queue
self.front = node
else

#  Add node at last level
self.rear.next = node
end

self.size += 1
self.rear = node
end

#  Delete front node of queue
def dequeue()
if (self.front != nil)
if (self.rear == self.front)
self.rear = nil
self.front = nil
else

self.front = self.front.next
end

self.size -= 1
end

end

def isSize()
return self.size
end

def isEmpty()
if (self.isSize() == 0)
return true
end

return false
end

def peek()
if (self.isSize() == 0)
return nil
else

return self.front
end

end

end

class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_accessor :root
def initialize()
self.root = nil
end

def diagonalTraversal()
if (self.root == nil)
print("Empty Tree\n")
return
end

count = 0
temp = nil
#  Empty Queue
record = MyQueue.new()
#  Use to managing a new line
track = Array.new(2) {0}
record.enqueue(self.root)
while (record.isEmpty() == false)
#  Collect Tree node
temp = record.peek().data
while (temp != nil)
print("  ", (temp.data))
if (temp.left != nil)
count += 1
record.enqueue(temp.left)
end

#  Visit to right child
temp = temp.right
end

#  Logic to include new line
if (track[0] == 0)
#  Include new line
print("\n")
track[1] += count
track[0] = track[1] - 1
track[1] = 0
else

track[0] -= 1
track[1] += count
end

count = 0
#  Remove front node
record.dequeue()
end

end

end

def main()
tree = BinaryTree.new()
#         1
#       /   \
#      2     3
#     / \   / \
#    3   4 6   5
#       /   \   \
#     -7     4   2
#     /     / \
#    9     1  -2
#         /     \
#       -5       12
#       /       /
#      6       4
# -----------------------
#    Binary Tree
# -----------------------
tree.root = TreeNode.new(1)
tree.root.left = TreeNode.new(2)
tree.root.right = TreeNode.new(3)
tree.root.left.left = TreeNode.new(3)
tree.root.left.right = TreeNode.new(4)
tree.root.left.right.left = TreeNode.new(-7)
tree.root.left.right.left.left = TreeNode.new(9)
tree.root.right.left = TreeNode.new(6)
tree.root.right.right = TreeNode.new(5)
tree.root.right.left.right = TreeNode.new(4)
tree.root.right.right.right = TreeNode.new(2)
tree.root.right.left.right.left = TreeNode.new(1)
tree.root.right.left.right.right = TreeNode.new(-2)
tree.root.right.left.right.right.right = TreeNode.new(12)
tree.root.right.left.right.left.left = TreeNode.new(-5)
tree.root.right.left.right.left.left.left = TreeNode.new(6)
tree.root.right.left.right.right.right.left = TreeNode.new(-4)
#  Test
tree.diagonalTraversal()
end

main()``````

#### Output

``````  1  3  5  2
2  4  6  4  -2  12
3  -7  1  -4
9  -5
6
``````
``````/*
Scala program
Iterative diagonal traversal of binary tree
*/
// Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data, null, null);
}
}
class QNode(var data: TreeNode,
var next: QNode)
{
def this(data: TreeNode)
{
this(data, null);
}
}
// Define custom queue class
class MyQueue(var front: QNode,
var rear: QNode,
var size: Int)
{
def this()
{
this(null, null, 0);
}
// Add a new node at last of queue
def enqueue(data: TreeNode): Unit = {
var node: QNode = new QNode(data);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size += 1;
this.rear = node;
}
// Delete front node of queue
def dequeue(): Unit = {
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size -= 1;
}
}
def isSize(): Int = {
return this.size;
}
def isEmpty(): Boolean = {
if (this.isSize() == 0)
{
return true;
}
return false;
}
def peek(): QNode = {
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front;
}
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def diagonalTraversal(): Unit = {
if (this.root == null)
{
print("Empty Tree\n");
return;
}
var count: Int = 0;
var temp: TreeNode = null;
// Empty Queue
var record: MyQueue = new MyQueue();
// Use to managing a new line
var track: Array[Int] = Array.fill[Int](2)(0);
track(0) = 0;
track(1) = 0;
record.enqueue(this.root);
while (record.isEmpty() == false)
{
// Collect Tree node
temp = record.peek().data;
while (temp != null)
{
print("  " + (temp.data));
if (temp.left != null)
{
count += 1;
record.enqueue(temp.left);
}
// Visit to right child
temp = temp.right;
}
// Logic to include new line
if (track(0) == 0)
{
// Include new line
print("\n");
track(1) += count;
track(0) = track(1) - 1;
track(1) = 0;
}
else
{
track(0) -= 1;
track(1) += count;
}
count = 0;
// Remove front node
record.dequeue();
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
1
/   \
2     3
/ \   / \
3   4 6   5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       4
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(-2);
tree.root.right.left.right.right.right = new TreeNode(12);
tree.root.right.left.right.left.left = new TreeNode(-5);
tree.root.right.left.right.left.left.left = new TreeNode(6);
tree.root.right.left.right.right.right.left = new TreeNode(-4);
// Test
tree.diagonalTraversal();
}
}``````

#### Output

``````  1  3  5  2
2  4  6  4  -2  12
3  -7  1  -4
9  -5
6``````
``````/*
Swift 4 program
Iterative diagonal traversal of binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class QNode
{
var data: TreeNode? ;
var next: QNode? ;
init(_ data: TreeNode? )
{
self.data = data;
self.next = nil;
}
}
// Define custom queue class
class MyQueue
{
var front: QNode? ;
var rear: QNode? ;
var size: Int;
init()
{
self.front = nil;
self.rear = nil;
self.size = 0;
}
// Add a new node at last of queue
func enqueue(_ data: TreeNode? )
{
let node: QNode = QNode(data);
if (self.front == nil)
{
// When first node of queue
self.front = node;
}
else
{
// Add node at last level
self.rear!.next = node;
}
self.size += 1;
self.rear = node;
}
// Delete front node of queue
func dequeue()
{
if (self.front  != nil)
{
if (self.rear === self.front)
{
self.rear = nil;
self.front = nil;
}
else
{
self.front = self.front!.next;
}
self.size -= 1;
}
}
func isSize() -> Int
{
return self.size;
}
func isEmpty() -> Bool
{
if (self.isSize() == 0)
{
return true;
}
return false;
}
func peek() -> QNode?
{
if (self.isSize() == 0)
{
return nil;
}
else
{
return self.front;
}
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func diagonalTraversal()
{
if (self.root == nil)
{
print("Empty Tree");
return;
}
var count: Int = 0;
var temp: TreeNode? = nil;
// Empty Queue
let record: MyQueue = MyQueue();
// Use to managing a new line
var track: [Int] = Array(repeating: 0, count: 2);
record.enqueue(self.root);
while (record.isEmpty() == false)
{
// Collect Tree node
temp = record.peek()!.data;
while (temp  != nil)
{
print("  ", (temp!.data), terminator: "");
if (temp!.left  != nil)
{
count += 1;
record.enqueue(temp!.left);
}
// Visit to right child
temp = temp!.right;
}
// Logic to include new line
if (track[0] == 0)
{
// Include new line
print(terminator: "\n");
track[1] += count;
track[0] = track[1] - 1;
track[1] = 0;
}
else
{
track[0] -= 1;
track[1] += count;
}
count = 0;
// Remove front node
record.dequeue();
}
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
1
/   \
2     3
/ \   / \
3   4 6   5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       4
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(1);
tree.root!.left = TreeNode(2);
tree.root!.right = TreeNode(3);
tree.root!.left!.left = TreeNode(3);
tree.root!.left!.right = TreeNode(4);
tree.root!.left!.right!.left = TreeNode(-7);
tree.root!.left!.right!.left!.left = TreeNode(9);
tree.root!.right!.left = TreeNode(6);
tree.root!.right!.right = TreeNode(5);
tree.root!.right!.left!.right = TreeNode(4);
tree.root!.right!.right!.right = TreeNode(2);
tree.root!.right!.left!.right!.left = TreeNode(1);
tree.root!.right!.left!.right!.right = TreeNode(-2);
tree.root!.right!.left!.right!.right!.right = TreeNode(12);
tree.root!.right!.left!.right!.left!.left = TreeNode(-5);
tree.root!.right!.left!.right!.left!.left!.left = TreeNode(6);
tree.root!.right!.left!.right!.right!.right!.left = TreeNode(-4);
// Test
tree.diagonalTraversal();
}
main();``````

#### Output

``````   1   3   5   2
2   4   6   4   -2   12
3   -7   1   -4
9   -5
6``````
``````/*
Kotlin program
Iterative diagonal traversal of binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class QNode
{
var data: TreeNode ? ;
var next: QNode ? ;
constructor(data: TreeNode ? )
{
this.data = data;
this.next = null;
}
}
// Define custom queue class
class MyQueue
{
var front: QNode ? ;
var rear: QNode ? ;
var size: Int;
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
fun enqueue(data: TreeNode ? ): Unit
{
val node: QNode = QNode(data);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear?.next = node;
}
this.size += 1;
this.rear = node;
}
// Delete front node of queue
fun dequeue(): Unit
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front?.next;
}
this.size -= 1;
}
}
fun isSize(): Int
{
return this.size;
}
fun isEmpty(): Boolean
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
fun peek(): QNode ?
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front;
}
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun diagonalTraversal(): Unit
{
if (this.root == null)
{
print("Empty Tree\n");
return;
}
var count: Int = 0;
var temp: TreeNode ? ;
// Empty Queue
val record: MyQueue = MyQueue();
// Use to managing a new line
var track: Array < Int > = Array(2)
{
0
};
record.enqueue(this.root);
while (record.isEmpty() == false)
{
// Collect Tree node
temp = record.peek()?.data;
while (temp != null)
{
print("  " + (temp.data));
if (temp.left != null)
{
count += 1;
record.enqueue(temp.left);
}
// Visit to right child
temp = temp.right;
}
// Logic to include new line
if (track[0] == 0)
{
// Include new line
print("\n");
track[1] += count;
track[0] = track[1] - 1;
track[1] = 0;
}
else
{
track[0] -= 1;
track[1] += count;
}
count = 0;
// Remove front node
record.dequeue();
}
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinaryTree = BinaryTree();
/*
1
/   \
2     3
/ \   / \
3   4 6   5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       4
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(1);
tree.root?.left = TreeNode(2);
tree.root?.right = TreeNode(3);
tree.root?.left?.left = TreeNode(3);
tree.root?.left?.right = TreeNode(4);
tree.root?.left?.right?.left = TreeNode(-7);
tree.root?.left?.right?.left?.left = TreeNode(9);
tree.root?.right?.left = TreeNode(6);
tree.root?.right?.right = TreeNode(5);
tree.root?.right?.left?.right = TreeNode(4);
tree.root?.right?.right?.right = TreeNode(2);
tree.root?.right?.left?.right?.left = TreeNode(1);
tree.root?.right?.left?.right?.right = TreeNode(-2);
tree.root?.right?.left?.right?.right?.right = TreeNode(12);
tree.root?.right?.left?.right?.left?.left = TreeNode(-5);
tree.root?.right?.left?.right?.left?.left?.left = TreeNode(6);
tree.root?.right?.left?.right?.right?.right?.left = TreeNode(-4);
// Test
tree.diagonalTraversal();
}``````

#### Output

``````  1  3  5  2
2  4  6  4  -2  12
3  -7  1  -4
9  -5
6``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.