# Find kth node in diagonal traversal of binary tree

Here given code implementation process.

``````/*
Java program
Find kth node in 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 findKthDiagonal(int k)
{
if (k <= 0)
{
System.out.print("\n Invalid k " + k);
return;
}
if (this.root == null)
{
System.out.print("Empty Tree\n");
return;
}
int count = 0;
TreeNode temp = null;
TreeNode result = null;
// Empty Queue
MyQueue record = new MyQueue();
// Add first element
record.enqueue(this.root);
while (record.isEmpty() == false)
{
// Collect Tree node
temp = record.peek().data;
while (temp != null && result == null)
{
count++;
if (temp.left != null)
{
record.enqueue(temp.left);
}
if (count == k)
{
result = temp;
}
// Visit to right child
temp = temp.right;
}
// Remove front node
record.dequeue();
}
if (result == null)
{
System.out.print("\n " + k +
"th diagonal element are not exist\n");
}
else
{
System.out.println("\n " + k +
"th diagonal element is : " +
(result.data));
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
1
/   \
-8    13
/ \   / \
3  11 16  5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       14
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(-8);
tree.root.right = new TreeNode(13);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(11);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(16);
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(14);
// Test
// Diagonal traversal
// [1 13 5 2 -8 11 16 4 -2 12 3 -7 1 14 9 -5 6]
// k = 3
// Result = 5
tree.findKthDiagonal(3);
// k = 7
// Result = 16
tree.findKthDiagonal(7);
// k = 19
// Result = None
tree.findKthDiagonal(19);
// k = 13
// Result = 1
tree.findKthDiagonal(13);
}
}``````

#### Output

`````` 3th diagonal element is : 5

7th diagonal element is : 16

19th diagonal element are not exist

13th diagonal element is : 1``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ program
Find kth node in 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 findKthDiagonal(int k)
{
if (k <= 0)
{
cout << "\n Invalid k " << k;
return;
}
if (this->root == NULL)
{
cout << "Empty Tree\n";
return;
}
int count = 0;
TreeNode *temp = NULL;
TreeNode *result = NULL;
// Empty Queue
MyQueue *record = new MyQueue();
// Add first element
record->enqueue(this->root);
while (record->isEmpty() == false)
{
// Collect Tree node
temp = record->peek()->data;
while (temp != NULL && result == NULL)
{
count++;
if (temp->left != NULL)
{
record->enqueue(temp->left);
}
if (count == k)
{
result = temp;
}
// Visit to right child
temp = temp->right;
}
// Remove front node
record->dequeue();
}
if (result == NULL)
{
cout << "\n " << k
<< "th diagonal element are not exist\n";
}
else
{
cout << "\n " << k
<< "th diagonal element is : "
<< (result->data) << endl;
}
}
};
int main()
{
BinaryTree *tree = new BinaryTree();
/*
1
/   \
-8    13
/ \   / \
3  11 16  5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       14
-----------------------
Binary Tree
-----------------------
*/
tree->root = new TreeNode(1);
tree->root->left = new TreeNode(-8);
tree->root->right = new TreeNode(13);
tree->root->left->left = new TreeNode(3);
tree->root->left->right = new TreeNode(11);
tree->root->left->right->left = new TreeNode(-7);
tree->root->left->right->left->left = new TreeNode(9);
tree->root->right->left = new TreeNode(16);
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(14);
// Test
// Diagonal traversal
// [1 13 5 2 -8 11 16 4 -2 12 3 -7 1 14 9 -5 6]
// k = 3
// Result = 5
tree->findKthDiagonal(3);
// k = 7
// Result = 16
tree->findKthDiagonal(7);
// k = 19
// Result = None
tree->findKthDiagonal(19);
// k = 13
// Result = 1
tree->findKthDiagonal(13);
return 0;
}``````

#### Output

`````` 3th diagonal element is : 5

7th diagonal element is : 16

19th diagonal element are not exist

13th diagonal element is : 1``````
``````// Include namespace system
using System;
/*
Csharp program
Find kth node in 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 findKthDiagonal(int k)
{
if (k <= 0)
{
Console.Write("\n Invalid k " + k);
return;
}
if (this.root == null)
{
Console.Write("Empty Tree\n");
return;
}
int count = 0;
TreeNode temp = null;
TreeNode result = null;
// Empty Queue
MyQueue record = new MyQueue();
// Add first element
record.enqueue(this.root);
while (record.isEmpty() == false)
{
// Collect Tree node
temp = record.peek().data;
while (temp != null && result == null)
{
count++;
if (temp.left != null)
{
record.enqueue(temp.left);
}
if (count == k)
{
result = temp;
}
// Visit to right child
temp = temp.right;
}
// Remove front node
record.dequeue();
}
if (result == null)
{
Console.Write("\n " + k +
"th diagonal element are not exist\n");
}
else
{
Console.WriteLine("\n " + k +
"th diagonal element is : " +
(result.data));
}
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
1
/   \
-8    13
/ \   / \
3  11 16  5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       14
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(-8);
tree.root.right = new TreeNode(13);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(11);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(16);
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(14);
// Test
// Diagonal traversal
// [1 13 5 2 -8 11 16 4 -2 12 3 -7 1 14 9 -5 6]
// k = 3
// Result = 5
tree.findKthDiagonal(3);
// k = 7
// Result = 16
tree.findKthDiagonal(7);
// k = 19
// Result = None
tree.findKthDiagonal(19);
// k = 13
// Result = 1
tree.findKthDiagonal(13);
}
}``````

#### Output

`````` 3th diagonal element is : 5

7th diagonal element is : 16

19th diagonal element are not exist

13th diagonal element is : 1``````
``````package main
import "fmt"
/*
Go program
Find kth node in 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) findKthDiagonal(k int) {
if k <= 0 {
fmt.Print("\n Invalid k ", k)
return
}
if this.root == nil {
fmt.Print("Empty Tree\n")
return
}
var count int = 0
var temp * TreeNode = nil
var result * TreeNode = nil
// Empty Queue
var record * MyQueue = getMyQueue()
// Add first element
record.enqueue(this.root)
for (record.isEmpty() == false) {
// Collect Tree node
temp = record.peek().data
for (temp != nil && result == nil) {
count++
if temp.left != nil {
record.enqueue(temp.left)
}
if count == k {
result = temp
}
// Visit to right child
temp = temp.right
}
// Remove front node
record.dequeue()
}
if result == nil {
fmt.Print("\n ", k,
"th diagonal element are not exist\n")
} else {
fmt.Println("\n ", k,
"th diagonal element is : ", (result.data))
}
}
func main() {
var tree * BinaryTree = getBinaryTree()
/*
1
/   \
-8    13
/ \   / \
3  11 16  5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       14
-----------------------
Binary Tree
-----------------------
*/
tree.root = getTreeNode(1)
tree.root.left = getTreeNode(-8)
tree.root.right = getTreeNode(13)
tree.root.left.left = getTreeNode(3)
tree.root.left.right = getTreeNode(11)
tree.root.left.right.left = getTreeNode(-7)
tree.root.left.right.left.left = getTreeNode(9)
tree.root.right.left = getTreeNode(16)
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(14)
// Test
// Diagonal traversal
// [1 13 5 2 -8 11 16 4 -2 12 3 -7 1 14 9 -5 6]
// k = 3
// Result = 5
tree.findKthDiagonal(3)
// k = 7
// Result = 16
tree.findKthDiagonal(7)
// k = 19
// Result = None
tree.findKthDiagonal(19)
// k = 13
// Result = 1
tree.findKthDiagonal(13)
}``````

#### Output

`````` 3 th diagonal element is : 5

7 th diagonal element is : 16

19 th diagonal element are not exist

13 th diagonal element is : 1``````
``````<?php
/*
Php program
Find kth node in 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 findKthDiagonal(\$k)
{
if (\$k <= 0)
{
echo("\n Invalid k ".\$k);
return;
}
if (\$this->root == NULL)
{
echo("Empty Tree\n");
return;
}
\$count = 0;
\$temp = NULL;
\$result = NULL;
// Empty Queue
\$record = new MyQueue();
// Add first element
\$record->enqueue(\$this->root);
while (\$record->isEmpty() == false)
{
// Collect Tree node
\$temp = \$record->peek()->data;
while (\$temp != NULL && \$result == NULL)
{
\$count++;
if (\$temp->left != NULL)
{
\$record->enqueue(\$temp->left);
}
if (\$count == \$k)
{
\$result = \$temp;
}
// Visit to right child
\$temp = \$temp->right;
}
// Remove front node
\$record->dequeue();
}
if (\$result == NULL)
{
echo("\n ".\$k.
"th diagonal element are not exist\n");
}
else
{
echo("\n ".\$k.
"th diagonal element is : ".(\$result->data).
"\n");
}
}
}

function main()
{
\$tree = new BinaryTree();
/*
1
/   \
-8    13
/ \   / \
3  11 16  5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       14
-----------------------
Binary Tree
-----------------------
*/
\$tree->root = new TreeNode(1);
\$tree->root->left = new TreeNode(-8);
\$tree->root->right = new TreeNode(13);
\$tree->root->left->left = new TreeNode(3);
\$tree->root->left->right = new TreeNode(11);
\$tree->root->left->right->left = new TreeNode(-7);
\$tree->root->left->right->left->left = new TreeNode(9);
\$tree->root->right->left = new TreeNode(16);
\$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(14);
// Test
// Diagonal traversal
// [1 13 5 2 -8 11 16 4 -2 12 3 -7 1 14 9 -5 6]
// k = 3
// Result = 5
\$tree->findKthDiagonal(3);
// k = 7
// Result = 16
\$tree->findKthDiagonal(7);
// k = 19
// Result = None
\$tree->findKthDiagonal(19);
// k = 13
// Result = 1
\$tree->findKthDiagonal(13);
}
main();``````

#### Output

`````` 3th diagonal element is : 5

7th diagonal element is : 16

19th diagonal element are not exist

13th diagonal element is : 1``````
``````/*
Node JS program
Find kth node in 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;
}
findKthDiagonal(k)
{
if (k <= 0)
{
process.stdout.write("\n Invalid k " + k);
return;
}
if (this.root == null)
{
process.stdout.write("Empty Tree\n");
return;
}
var count = 0;
var temp = null;
var result = null;
// Empty Queue
var record = new MyQueue();
// Add first element
record.enqueue(this.root);
while (record.isEmpty() == false)
{
// Collect Tree node
temp = record.peek().data;
while (temp != null && result == null)
{
count++;
if (temp.left != null)
{
record.enqueue(temp.left);
}
if (count == k)
{
result = temp;
}
// Visit to right child
temp = temp.right;
}
// Remove front node
record.dequeue();
}
if (result == null)
{
process.stdout.write("\n " + k +
"th diagonal element are not exist\n");
}
else
{
console.log("\n " + k +
"th diagonal element is : " +
(result.data));
}
}
}

function main()
{
var tree = new BinaryTree();
/*
1
/   \
-8    13
/ \   / \
3  11 16  5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       14
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(-8);
tree.root.right = new TreeNode(13);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(11);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(16);
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(14);
// Test
// Diagonal traversal
// [1 13 5 2 -8 11 16 4 -2 12 3 -7 1 14 9 -5 6]
// k = 3
// Result = 5
tree.findKthDiagonal(3);
// k = 7
// Result = 16
tree.findKthDiagonal(7);
// k = 19
// Result = None
tree.findKthDiagonal(19);
// k = 13
// Result = 1
tree.findKthDiagonal(13);
}
main();``````

#### Output

`````` 3th diagonal element is : 5

7th diagonal element is : 16

19th diagonal element are not exist

13th diagonal element is : 1``````
``````#    Python 3 program
#    Find kth node in 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 findKthDiagonal(self, k) :
if (k <= 0) :
print("\n Invalid k ", k, end = "")
return

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

count = 0
temp = None
result = None
#  Empty Queue
record = MyQueue()
#  Add first element
record.enqueue(self.root)
while (record.isEmpty() == False) :
#  Collect Tree node
temp = record.peek().data
while (temp != None and result == None) :
count += 1
if (temp.left != None) :
record.enqueue(temp.left)

if (count == k) :
result = temp

#  Visit to right child
temp = temp.right

#  Remove front node
record.dequeue()

if (result == None) :
print("\n ", k ,"th diagonal element are not exist")
else :
print("\n ", k ,"th diagonal element is : ", (result.data))

def main() :
tree = BinaryTree()
#         1
#       /   \
#     -8    13
#     / \   / \
#    3  11 16  5
#       /   \   \
#     -7     4   2
#     /     / \
#    9     1  -2
#         /     \
#       -5       12
#       /       /
#      6       14
# -----------------------
#    Binary Tree
# -----------------------
tree.root = TreeNode(1)
tree.root.left = TreeNode(-8)
tree.root.right = TreeNode(13)
tree.root.left.left = TreeNode(3)
tree.root.left.right = TreeNode(11)
tree.root.left.right.left = TreeNode(-7)
tree.root.left.right.left.left = TreeNode(9)
tree.root.right.left = TreeNode(16)
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(14)
#  Test
#  Diagonal traversal
#  [1 13 5 2 -8 11 16 4 -2 12 3 -7 1 14 9 -5 6]
#  k = 3
#  Result = 5
tree.findKthDiagonal(3)
#  k = 7
#  Result = 16
tree.findKthDiagonal(7)
#  k = 19
#  Result = None
tree.findKthDiagonal(19)
#  k = 13
#  Result = 1
tree.findKthDiagonal(13)

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

#### Output

``````  3 th diagonal element is :  5

7 th diagonal element is :  16

19 th diagonal element are not exist

13 th diagonal element is :  1``````
``````#    Ruby program
#    Find kth node in diagonal traversal of binary tree

#  Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
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_reader :data, :next
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_reader :front, :rear, :size
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_reader :root
attr_accessor :root
def initialize()
self.root = nil
end

def findKthDiagonal(k)
if (k <= 0)
print("\n Invalid k ", k)
return
end

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

count = 0
temp = nil
result = nil
#  Empty Queue
record = MyQueue.new()
#  Add first element
record.enqueue(self.root)
while (record.isEmpty() == false)
#  Collect Tree node
temp = record.peek().data
while (temp != nil && result == nil)
count += 1
if (temp.left != nil)
record.enqueue(temp.left)
end

if (count == k)
result = temp
end

#  Visit to right child
temp = temp.right
end

#  Remove front node
record.dequeue()
end

if (result == nil)
print("\n ", k ,
"th diagonal element are not exist\n")
else

print("\n ", k ,
"th diagonal element is : ",
(result.data), "\n")
end

end

end

def main()
tree = BinaryTree.new()
#         1
#       /   \
#     -8    13
#     / \   / \
#    3  11 16  5
#       /   \   \
#     -7     4   2
#     /     / \
#    9     1  -2
#         /     \
#       -5       12
#       /       /
#      6       14
# -----------------------
#    Binary Tree
# -----------------------
tree.root = TreeNode.new(1)
tree.root.left = TreeNode.new(-8)
tree.root.right = TreeNode.new(13)
tree.root.left.left = TreeNode.new(3)
tree.root.left.right = TreeNode.new(11)
tree.root.left.right.left = TreeNode.new(-7)
tree.root.left.right.left.left = TreeNode.new(9)
tree.root.right.left = TreeNode.new(16)
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(14)
#  Test
#  Diagonal traversal
#  [1 13 5 2 -8 11 16 4 -2 12 3 -7 1 14 9 -5 6]
#  k = 3
#  Result = 5
tree.findKthDiagonal(3)
#  k = 7
#  Result = 16
tree.findKthDiagonal(7)
#  k = 19
#  Result = None
tree.findKthDiagonal(19)
#  k = 13
#  Result = 1
tree.findKthDiagonal(13)
end

main()``````

#### Output

`````` 3th diagonal element is : 5

7th diagonal element is : 16

19th diagonal element are not exist

13th diagonal element is : 1
``````
``````/*
Scala program
Find kth node in 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 findKthDiagonal(k: Int): Unit = {
if (k <= 0)
{
print("\n Invalid k " + k);
return;
}
if (this.root == null)
{
print("Empty Tree\n");
return;
}
var count: Int = 0;
var temp: TreeNode = null;
var result: TreeNode = null;
// Empty Queue
var record: MyQueue = new MyQueue();
// Add first element
record.enqueue(this.root);
while (record.isEmpty() == false)
{
// Collect Tree node
temp = record.peek().data;
while (temp != null && result == null)
{
count += 1;
if (temp.left != null)
{
record.enqueue(temp.left);
}
if (count == k)
{
result = temp;
}
// Visit to right child
temp = temp.right;
}
// Remove front node
record.dequeue();
}
if (result == null)
{
print("\n " + k + "th diagonal element are not exist\n");
}
else
{
println("\n " + k +
"th diagonal element is : " + (result.data));
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
1
/   \
-8    13
/ \   / \
3  11 16  5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       14
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(-8);
tree.root.right = new TreeNode(13);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(11);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(16);
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(14);
// Test
// Diagonal traversal
// [1 13 5 2 -8 11 16 4 -2 12 3 -7 1 14 9 -5 6]
// k = 3
// Result = 5
tree.findKthDiagonal(3);
// k = 7
// Result = 16
tree.findKthDiagonal(7);
// k = 19
// Result = None
tree.findKthDiagonal(19);
// k = 13
// Result = 1
tree.findKthDiagonal(13);
}
}``````

#### Output

`````` 3th diagonal element is : 5

7th diagonal element is : 16

19th diagonal element are not exist

13th diagonal element is : 1``````
``````/*
Swift 4 program
Find kth node in 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 findKthDiagonal(_ k: Int)
{
if (k <= 0)
{
print("\n Invalid k ", k, terminator: "");
return;
}
if (self.root == nil)
{
print("Empty Tree");
return;
}
var count: Int = 0;
var temp: TreeNode? = nil;
var result: TreeNode? = nil;
// Empty Queue
let record: MyQueue = MyQueue();
// Add first element
record.enqueue(self.root);
while (record.isEmpty() == false)
{
// Collect Tree node
temp = record.peek()!.data;
while (temp  != nil && result == nil)
{
count += 1;
if (temp!.left  != nil)
{
record.enqueue(temp!.left);
}
if (count == k)
{
result = temp;
}
// Visit to right child
temp = temp!.right;
}
// Remove front node
record.dequeue();
}
if (result == nil)
{
print("\n ", k ,"th diagonal element are not exist");
}
else
{
print("\n ", k ,
"th diagonal element is : ",
(result!.data));
}
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
1
/   \
-8    13
/ \   / \
3  11 16  5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       14
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(1);
tree.root!.left = TreeNode(-8);
tree.root!.right = TreeNode(13);
tree.root!.left!.left = TreeNode(3);
tree.root!.left!.right = TreeNode(11);
tree.root!.left!.right!.left = TreeNode(-7);
tree.root!.left!.right!.left!.left = TreeNode(9);
tree.root!.right!.left = TreeNode(16);
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(14);
// Test
// Diagonal traversal
// [1 13 5 2 -8 11 16 4 -2 12 3 -7 1 14 9 -5 6]
// k = 3
// Result = 5
tree.findKthDiagonal(3);
// k = 7
// Result = 16
tree.findKthDiagonal(7);
// k = 19
// Result = None
tree.findKthDiagonal(19);
// k = 13
// Result = 1
tree.findKthDiagonal(13);
}
main();``````

#### Output

``````  3 th diagonal element is :  5

7 th diagonal element is :  16

19 th diagonal element are not exist

13 th diagonal element is :  1``````
``````/*
Kotlin program
Find kth node in 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 findKthDiagonal(k: Int): Unit
{
if (k <= 0)
{
print("\n Invalid k " + k);
return;
}
if (this.root == null)
{
print("Empty Tree\n");
return;
}
var count: Int = 0;
var temp: TreeNode ?;
var result: TreeNode ? = null;
// Empty Queue
val record: MyQueue = MyQueue();
// Add first element
record.enqueue(this.root);
while (record.isEmpty() == false)
{
// Collect Tree node
temp = record.peek()?.data;
while (temp != null && result == null)
{
count += 1;
if (temp.left != null)
{
record.enqueue(temp.left);
}
if (count == k)
{
result = temp;
}
// Visit to right child
temp = temp.right;
}
// Remove front node
record.dequeue();
}
if (result == null)
{
print("\n " + k +
"th diagonal element are not exist\n");
}
else
{
println("\n " + k +
"th diagonal element is : " +
(result.data));
}
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinaryTree = BinaryTree();
/*
1
/   \
-8    13
/ \   / \
3  11 16  5
/   \   \
-7     4   2
/     / \
9     1  -2
/     \
-5       12
/       /
6       14
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(1);
tree.root?.left = TreeNode(-8);
tree.root?.right = TreeNode(13);
tree.root?.left?.left = TreeNode(3);
tree.root?.left?.right = TreeNode(11);
tree.root?.left?.right?.left = TreeNode(-7);
tree.root?.left?.right?.left?.left = TreeNode(9);
tree.root?.right?.left = TreeNode(16);
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(14);
// Test
// Diagonal traversal
// [1 13 5 2 -8 11 16 4 -2 12 3 -7 1 14 9 -5 6]
// k = 3
// Result = 5
tree.findKthDiagonal(3);
// k = 7
// Result = 16
tree.findKthDiagonal(7);
// k = 19
// Result = None
tree.findKthDiagonal(19);
// k = 13
// Result = 1
tree.findKthDiagonal(13);
}``````

#### Output

`````` 3th diagonal element is : 5

7th diagonal element is : 16

19th diagonal element are not exist

13th diagonal element is : 1``````

## Comment

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.