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;
		// Add first element
		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;
		// Add first element
		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;
		// Add first element
		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)
	// Add first element
	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;
		// Add first element
		$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;
		// Add first element
		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
		#  Add first element
		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_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 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}
		#  Add first element
		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;
		// Add first element
		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);
		// Add first element
		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
		};
		// Add first element
		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.

New Comment




© 2021, kalkicode.com, All rights reserved