Construct Diamond Tree

Diamond Tree

Here given code implementation process.

/*
    C Program 
    Construct Diamond Tree
*/
#include <stdio.h>
#include <stdlib.h>
struct TreeNode
{
	int key;
	struct TreeNode *left;
	struct TreeNode *right;
};
struct BinaryTree
{
	struct TreeNode *root;
};
struct QNode
{
	struct TreeNode *n;
	struct QNode *next;
};
struct MyQueue
{
	int size;
	struct QNode *front;
	struct QNode *rear;
};
struct BinaryTree *makeTree()
{
	struct BinaryTree *tree = (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
	if (tree == NULL)
	{
		printf("\nMemory Overflow, when creating a new BinaryTree\n");
	}
	else
	{
		tree->root = NULL;
	}
	return tree;
}
struct MyQueue *makeQueue()
{
	// Create dynamic node of MyQueue
	struct MyQueue *q = (struct MyQueue *) malloc(sizeof(struct MyQueue));
	if (q == NULL)
	{
		printf("\n Memory Overflow, when creating a new Queue\n");
	}
	else
	{
		q->front = NULL;
		q->rear = NULL;
		q->size = 0;
	}
	return q;
}
int isSize(struct MyQueue *queue)
{
	return queue->size;
}
struct TreeNode *peek(struct MyQueue *q)
{
	if (isSize(q) == 0)
	{
		printf("\n Empty Queue");
		return NULL;
	}
	return q->front->n;
}
// Add new queue node
void enqueue(struct MyQueue *q, struct TreeNode *element)
{
	// Make a new Queue node
	struct QNode *node = (struct QNode *) malloc(sizeof(struct QNode));
	if (node != NULL)
	{
		// Set node values
		node->n = element;
		node->next = NULL;
		if (q->front == NULL)
		{
			q->front = node;
			q->rear = q->front;
		}
		else
		{
			q->rear->next = node;
			q->rear = node;
		}
		q->size++;
	}
	else
	{
		printf("\nMemory Overflow, when creating a new Queue Node\n");
	}
}
//Remove a queue elements
void dequeue(struct MyQueue *q)
{
	if (isSize(q) > 0)
	{
		struct QNode *remove = q->front;
		if (q->front == q->rear)
		{
			q->rear = NULL;
		}
		q->front = q->front->next;
		q->size = q->size - 1;
		remove->n = NULL;
		remove->next = NULL;
		//free node
		free(remove);
		remove = NULL;
	}
}
// Returns a new node of tree
struct TreeNode *newNode(int data)
{
	// Create dynamic node
	struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
	if (node != NULL)
	{
		//Set data and pointer values
		node->key = data;
		node->left = NULL;
		node->right = NULL;
	}
	else
	{
		//This is indicates, segmentation fault or memory overflow problem
		printf("Memory Overflow\n");
	}
	//return new node
	return node;
}
// Construct diamond tree 
struct BinaryTree *constructTree(int k)
{
	if (k <= 0)
	{
		return NULL;
	}
	// Define some counter variables
	int num = 1;
	int n = 0;
	// Construct binary tree
	struct BinaryTree *tree = makeTree();
	// Construct a queue
	struct MyQueue *q = makeQueue();
	struct TreeNode *auxiliary = NULL;
	// Create first node
	struct TreeNode *node = newNode(num);
	// set first node as root
	tree->root = node;
	// Add first node into the queue
	enqueue(q, node);
	// Construct Complete binary tree of K level
	while (k > 1)
	{
		n = isSize(q);
		while (n > 0)
		{
			node = peek(q);
			dequeue(q);
			// Add left node
			node->left = newNode(num + 1);
			// Add right node
			node->right = newNode(num + 2);
			// Add both constructed node into queue
			enqueue(q, node->left);
			enqueue(q, node->right);
			// Update counter value
			num += 2;
			n--;
		}
		// Reduce size
		k--;
	}
	// Construct bottom part of diamond tree
	while (isSize(q) > 1)
	{
		// Get first node
		node = peek(q);
		dequeue(q);
		// Get second node
		auxiliary = peek(q);
		dequeue(q);
		// Construct new node and append right side of first node
		node->right = newNode(node->key + auxiliary->key);
		// Connect new node with left of second node
		auxiliary->left = node->right;
		// Add constructor node into queue
		enqueue(q, node->right);
	}
	return tree;
}
// Level order traversal in given diamond tree
void printTree(struct TreeNode *root)
{
	struct MyQueue *q = makeQueue();
	// Insert first node of queue
	enqueue(q, root);
	int n = 0;
	// Define some auxiliary variable
	struct TreeNode *node = NULL;
	struct TreeNode *back = root;
	// Print diamond tree element in level order
	while (isSize(q) > 0)
	{
		// Get current queue size
		n = isSize(q);
		while (n > 0)
		{
			node = peek(q);
			// Remove front node of queue 
			dequeue(q);
			if (node->left != NULL && node->left != back)
			{
				back = node->left;
				enqueue(q, back);
			}
			if (node->right != NULL && node->right != back)
			{
				back = node->right;
				enqueue(q, back);
			}
			// Display level node
			printf("  %d", node->key);
			// Reduce size
			n--;
		}
		// When change level
		printf("\n");
	}
}
int main(int argc, char const *argv[])
{
	// Size of diamond tree
	int k = 4;
	struct BinaryTree *tree = constructTree(k);
	printTree(tree->root);
	return 0;
}

Output

  1
  2  3
  4  5  6  7
  8  9  10  11  12  13  14  15
  17  21  25  29
  38  54
  92
// Include header file
#include <iostream>
using namespace std;
/*
    C++ Program 
    Construct Diamond Tree
*/
// Binary Tree node
class TreeNode
{
	public: 
    int key;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int key)
	{
		// Set node value
		this->key = key;
		this->left = NULL;
		this->right = NULL;
	}
};
// Queue Node
class QNode
{
	public: TreeNode *n;
	QNode *next;
	QNode(TreeNode *n)
	{
		this->n = n;
		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 *n)
	{
		QNode *node = new QNode(n);
		if (this->front == NULL)
		{
			// When first node of queue
			this->front = node;
		}
		else
		{
			// Add node at last position
			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;
	}
	TreeNode *peek()
	{
		if (this->isSize() == 0)
		{
			return NULL;
		}
		else
		{
			return this->front->n;
		}
	}
};
class DiamondTree
{
	public: TreeNode *root;
	DiamondTree()
	{
		// Set root of tree
		this->root = NULL;
	}
	// Construct diamond tree
	TreeNode *constructTree(int k)
	{
		if (k <= 0)
		{
			return NULL;
		}
		// Define some counter variables
		int num = 1;
		int n = 0;
		// Construct a queue
		MyQueue q = MyQueue();
		TreeNode *auxiliary = NULL;
		// Create first node
		TreeNode *root = new TreeNode(num);
		TreeNode *node = root;
		// Add first node into the queue
		q.enQueue(node);
		// Construct Complete binary tree of K level
		while (k > 1)
		{
			// Reduce size
			n = q.isSize();
			while (n > 0)
			{
				node = q.peek();
				q.deQueue();
				// Add left node
				node->left = new TreeNode(num + 1);
				// Add right node
				node->right = new TreeNode(num + 2);
				// Add both constructed node into queue
				q.enQueue(node->left);
				q.enQueue(node->right);
				// Update counter value
				num += 2;
				n--;
			}
			k--;
		}
		// Construct bottom part of diamond tree
		while (q.isSize() > 1)
		{
			// Get first node
			node = q.peek();
			q.deQueue();
			// Get second node
			auxiliary = q.peek();
			q.deQueue();
			// Construct new node and append right side of first node
			node->right = new TreeNode(node->key + auxiliary->key);
			// Connect new node with left of second node
			auxiliary->left = node->right;
			// Add constructor node into queue
			q.enQueue(node->right);
		}
		return root;
	}
	// Level order traversal in given diamond tree
	void printTree(TreeNode *root)
	{
		MyQueue q = MyQueue();
		// Insert first node of queue
		q.enQueue(root);
		int n = 0;
		// Define some auxiliary variable
		TreeNode *node = NULL;
		TreeNode *back = root;
		// Print diamond tree element in level order
		while (q.isSize() > 0)
		{
			// Get current queue size
			n = q.isSize();
			while (n > 0)
			{
				// Reduce size
				node = q.peek();
				// Remove front node of queue
				q.deQueue();
				if (node->left != NULL && node->left != back)
				{
					back = node->left;
					q.enQueue(back);
				}
				if (node->right != NULL && node->right != back)
				{
					back = node->right;
					q.enQueue(back);
				}
				// Display level node
				cout << " " << node->key;
				n--;
			}
			// When change level
			cout << "\n";
		}
	}
};
int main()
{
	int k = 4;
	DiamondTree tree = DiamondTree();
	tree.root = tree.constructTree(k);
	tree.printTree(tree.root);
	return 0;
}

Output

 1
 2 3
 4 5 6 7
 8 9 10 11 12 13 14 15
 17 21 25 29
 38 54
 92
/*
    Java Program 
    Construct Diamond Tree
*/
// Binary Tree node
class TreeNode
{
	public int key;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int key)
	{
		// Set node value
		this.key = key;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
class QNode
{
	public TreeNode n;
	public QNode next;
	public QNode(TreeNode n)
	{
		this.n = n;
		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 n)
	{
		QNode node = new QNode(n);
		if (this.front == null)
		{
			// When first node of queue
			this.front = node;
		}
		else
		{
			// Add node at last position
			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 TreeNode peek()
	{
		if (this.isSize() == 0)
		{
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
}
public class DiamondTree
{
	public TreeNode root;
	public DiamondTree()
	{
		// Set root of tree
		this.root = null;
	}
	// Construct diamond tree 
	public TreeNode constructTree(int k)
	{
		if (k <= 0)
		{
			return null;
		}
		// Define some counter variables
		int num = 1;
		int n = 0;
		// Construct a queue
		MyQueue q = new MyQueue();
		TreeNode auxiliary = null;
		// Create first node
		TreeNode root = new TreeNode(num);
		TreeNode node = root;
		// Add first node into the queue
		q.enQueue(node);
		// Construct Complete binary tree of K level
		while (k > 1)
		{
			n = q.isSize();
			while (n > 0)
			{
				node = q.peek();
				q.deQueue();
				// Add left node
				node.left = new TreeNode(num + 1);
				// Add right node
				node.right = new TreeNode(num + 2);
				// Add both constructed node into queue
				q.enQueue(node.left);
				q.enQueue(node.right);
				// Update counter value
				num += 2;
				n--;
			}
			// Reduce size
			k--;
		}
		// Construct bottom part of diamond tree
		while (q.isSize() > 1)
		{
			// Get first node
			node = q.peek();
			q.deQueue();
			// Get second node
			auxiliary = q.peek();
			q.deQueue();
			// Construct new node and append right side of first node
			node.right = new TreeNode(node.key + auxiliary.key);
			// Connect new node with left of second node
			auxiliary.left = node.right;
			// Add constructor node into queue
			q.enQueue(node.right);
		}
		return root;
	}
	// Level order traversal in given diamond tree
	public void printTree(TreeNode root)
	{
		MyQueue q = new MyQueue();
		// Insert first node of queue
		q.enQueue(root);
		int n = 0;
		// Define some auxiliary variable
		TreeNode node = null;
		TreeNode back = root;
		// Print diamond tree element in level order
		while (q.isSize() > 0)
		{
			// Get current queue size
			n = q.isSize();
			while (n > 0)
			{
				node = q.peek();
				// Remove front node of queue 
				q.deQueue();
				if (node.left != null && node.left != back)
				{
					back = node.left;
					q.enQueue(back);
				}
				if (node.right != null && node.right != back)
				{
					back = node.right;
					q.enQueue(back);
				}
				// Display level node
				System.out.print(" " + node.key);
				// Reduce size
				n--;
			}
			// When change level
			System.out.print("\n");
		}
	}
	public static void main(String[] args)
	{
		int k = 4;
		DiamondTree tree = new DiamondTree();
		tree.root = tree.constructTree(k);
		tree.printTree(tree.root);
	}
}

Output

 1
 2 3
 4 5 6 7
 8 9 10 11 12 13 14 15
 17 21 25 29
 38 54
 92
// Include namespace system
using System;
/*
    C# Program 
    Construct Diamond Tree
*/
// Binary Tree node
public class TreeNode
{
	public int key;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int key)
	{
		// Set node value
		this.key = key;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
public class QNode
{
	public TreeNode n;
	public QNode next;
	public QNode(TreeNode n)
	{
		this.n = n;
		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 n)
	{
		QNode node = new QNode(n);
		if (this.front == null)
		{
			// When first node of queue
			this.front = node;
		}
		else
		{
			// Add node at last position
			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 TreeNode peek()
	{
		if (this.isSize() == 0)
		{
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
}
public class DiamondTree
{
	public TreeNode root;
	public DiamondTree()
	{
		// Set root of tree
		this.root = null;
	}
	// Construct diamond tree
	public TreeNode constructTree(int k)
	{
		if (k <= 0)
		{
			return null;
		}
		// Define some counter variables
		int num = 1;
		int n = 0;
		// Construct a queue
		MyQueue q = new MyQueue();
		TreeNode auxiliary = null;
		// Create first node
		TreeNode root = new TreeNode(num);
		TreeNode node = root;
		// Add first node into the queue
		q.enQueue(node);
		// Construct Complete binary tree of K level
		while (k > 1)
		{
			// Reduce size
			n = q.isSize();
			while (n > 0)
			{
				node = q.peek();
				q.deQueue();
				// Add left node
				node.left = new TreeNode(num + 1);
				// Add right node
				node.right = new TreeNode(num + 2);
				// Add both constructed node into queue
				q.enQueue(node.left);
				q.enQueue(node.right);
				// Update counter value
				num += 2;
				n--;
			}
			k--;
		}
		// Construct bottom part of diamond tree
		while (q.isSize() > 1)
		{
			// Get first node
			node = q.peek();
			q.deQueue();
			// Get second node
			auxiliary = q.peek();
			q.deQueue();
			// Construct new node and append right side of first node
			node.right = new TreeNode(node.key + auxiliary.key);
			// Connect new node with left of second node
			auxiliary.left = node.right;
			// Add constructor node into queue
			q.enQueue(node.right);
		}
		return root;
	}
	// Level order traversal in given diamond tree
	public void printTree(TreeNode root)
	{
		MyQueue q = new MyQueue();
		// Insert first node of queue
		q.enQueue(root);
		int n = 0;
		// Define some auxiliary variable
		TreeNode node = null;
		TreeNode back = root;
		// Print diamond tree element in level order
		while (q.isSize() > 0)
		{
			// Get current queue size
			n = q.isSize();
			while (n > 0)
			{
				// Reduce size
				node = q.peek();
				// Remove front node of queue
				q.deQueue();
				if (node.left != null && node.left != back)
				{
					back = node.left;
					q.enQueue(back);
				}
				if (node.right != null && node.right != back)
				{
					back = node.right;
					q.enQueue(back);
				}
				// Display level node
				Console.Write(" " + node.key);
				n--;
			}
			// When change level
			Console.Write("\n");
		}
	}
	public static void Main(String[] args)
	{
		int k = 4;
		DiamondTree tree = new DiamondTree();
		tree.root = tree.constructTree(k);
		tree.printTree(tree.root);
	}
}

Output

 1
 2 3
 4 5 6 7
 8 9 10 11 12 13 14 15
 17 21 25 29
 38 54
 92
<?php
/*
    Php Program 
    Construct Diamond Tree
*/
// Binary Tree node
class TreeNode
{
	public $key;
	public $left;
	public $right;

	function __construct($key)
	{
		// Set node value
		$this->key = $key;
		$this->left = null;
		$this->right = null;
	}
}
// Queue Node
class QNode
{
	public $n;
	public $next;

	function __construct($n)
	{
		$this->n = $n;
		$this->next = null;
	}
}
//Define custom queue class
class MyQueue
{
	public $front;
	public $rear;
	public $size;

	function __construct()
	{
		$this->front = null;
		$this->rear = null;
		$this->size = 0;
	}
	// Add a new node at last of queue
	public	function enQueue($n)
	{
		$node = new QNode($n);
		if ($this->front == null)
		{
			// When first node of queue
			$this->front = $node;
		}
		else
		{
			// Add node at last position
			$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 peek()
	{
		if ($this->isSize() == 0)
		{
			return null;
		}
		else
		{
			return $this->front->n;
		}
	}
}
class DiamondTree
{
	public $root;

	function __construct()
	{
		// Set root of tree
		$this->root = null;
	}
	// Construct diamond tree
	public	function constructTree($k)
	{
		if ($k <= 0)
		{
			return null;
		}
		// Define some counter variables
		$num = 1;
		$n = 0;
		// Construct a queue
		$q = new MyQueue();
		$auxiliary = null;
		// Create first node
		$root = new TreeNode($num);
		$node = $root;
		// Add first node into the queue
		$q->enQueue($node);
		// Construct Complete binary tree of K level
		while ($k > 1)
		{
			// Reduce size
			$n = $q->isSize();
			while ($n > 0)
			{
				$node = $q->peek();
				$q->deQueue();
				// Add left node
				$node->left = new TreeNode($num + 1);
				// Add right node
				$node->right = new TreeNode($num + 2);
				// Add both constructed node into queue
				$q->enQueue($node->left);
				$q->enQueue($node->right);
				// Update counter value
				$num += 2;
				$n--;
			}
			$k--;
		}
		// Construct bottom part of diamond tree
		while ($q->isSize() > 1)
		{
			// Get first node
			$node = $q->peek();
			$q->deQueue();
			// Get second node
			$auxiliary = $q->peek();
			$q->deQueue();
			// Construct new node and append right side of first node
			$node->right = new TreeNode($node->key + $auxiliary->key);
			// Connect new node with left of second node
			$auxiliary->left = $node->right;
			// Add constructor node into queue
			$q->enQueue($node->right);
		}
		return $root;
	}
	// Level order traversal in given diamond tree
	public	function printTree($root)
	{
		$q = new MyQueue();
		// Insert first node of queue
		$q->enQueue($root);
		$n = 0;
		// Define some auxiliary variable
		$node = null;
		$back = $root;
		// Print diamond tree element in level order
		while ($q->isSize() > 0)
		{
			// Get current queue size
			$n = $q->isSize();
			while ($n > 0)
			{
				// Reduce size
				$node = $q->peek();
				// Remove front node of queue
				$q->deQueue();
				if ($node->left != null && $node->left != $back)
				{
					$back = $node->left;
					$q->enQueue($back);
				}
				if ($node->right != null && $node->right != $back)
				{
					$back = $node->right;
					$q->enQueue($back);
				}
				// Display level node
				echo " ". $node->key;
				$n--;
			}
			// When change level
			echo "\n";
		}
	}
}

function main()
{
	$k = 4;
	$tree = new DiamondTree();
	$tree->root = $tree->constructTree($k);
	$tree->printTree($tree->root);
}
main();

Output

 1
 2 3
 4 5 6 7
 8 9 10 11 12 13 14 15
 17 21 25 29
 38 54
 92
/*
    Node Js Program 
    Construct Diamond Tree
*/
// Binary Tree node
class TreeNode
{
	constructor(key)
	{
		// Set node value
		this.key = key;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
class QNode
{
	constructor(n)
	{
		this.n = n;
		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(n)
	{
		var node = new QNode(n);
		if (this.front == null)
		{
			// When first node of queue
			this.front = node;
		}
		else
		{
			// Add node at last position
			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;
	}
	peek()
	{
		if (this.isSize() == 0)
		{
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
}
class DiamondTree
{
	constructor()
	{
		// Set root of tree
		this.root = null;
	}
	// Construct diamond tree
	constructTree(k)
	{
		if (k <= 0)
		{
			return null;
		}
		// Define some counter variables
		var num = 1;
		var n = 0;
		// Construct a queue
		var q = new MyQueue();
		var auxiliary = null;
		// Create first node
		var root = new TreeNode(num);
		var node = root;
		// Add first node into the queue
		q.enQueue(node);
		// Construct Complete binary tree of K level
		while (k > 1)
		{
			// Reduce size
			n = q.isSize();
			while (n > 0)
			{
				node = q.peek();
				q.deQueue();
				// Add left node
				node.left = new TreeNode(num + 1);
				// Add right node
				node.right = new TreeNode(num + 2);
				// Add both constructed node into queue
				q.enQueue(node.left);
				q.enQueue(node.right);
				// Update counter value
				num += 2;
				n--;
			}
			k--;
		}
		// Construct bottom part of diamond tree
		while (q.isSize() > 1)
		{
			// Get first node
			node = q.peek();
			q.deQueue();
			// Get second node
			auxiliary = q.peek();
			q.deQueue();
			// Construct new node and append right side of first node
			node.right = new TreeNode(node.key + auxiliary.key);
			// Connect new node with left of second node
			auxiliary.left = node.right;
			// Add constructor node into queue
			q.enQueue(node.right);
		}
		return root;
	}
	// Level order traversal in given diamond tree
	printTree(root)
	{
		var q = new MyQueue();
		// Insert first node of queue
		q.enQueue(root);
		var n = 0;
		// Define some auxiliary variable
		var node = null;
		var back = root;
		// Print diamond tree element in level order
		while (q.isSize() > 0)
		{
			// Get current queue size
			n = q.isSize();
			while (n > 0)
			{
				// Reduce size
				node = q.peek();
				// Remove front node of queue
				q.deQueue();
				if (node.left != null && node.left != back)
				{
					back = node.left;
					q.enQueue(back);
				}
				if (node.right != null && node.right != back)
				{
					back = node.right;
					q.enQueue(back);
				}
				// Display level node
				process.stdout.write(" " + node.key);
				n--;
			}
			// When change level
			process.stdout.write("\n");
		}
	}
}

function main()
{
	var k = 4;
	var tree = new DiamondTree();
	tree.root = tree.constructTree(k);
	tree.printTree(tree.root);
}
main();

Output

 1
 2 3
 4 5 6 7
 8 9 10 11 12 13 14 15
 17 21 25 29
 38 54
 92
#  Python 3 Program 
#  Construct Diamond Tree

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

#  Queue Node
class QNode :
	
	def __init__(self, n) :
		self.n = n
		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, n) :
		node = QNode(n)
		if (self.front == None) :
			#  When first node of queue
			self.front = node
		else :
			#  Add node at last position
			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 peek(self) :
		if (self.isSize() == 0) :
			return None
		else :
			return self.front.n
		
	

class DiamondTree :
	
	def __init__(self) :
		#  Set root of tree
		self.root = None
	
	#  Construct diamond tree 
	def constructTree(self, k) :
		if (k <= 0) :
			return None
		
		#  Define some counter variables
		num = 1
		n = 0
		#  Construct a queue
		q = MyQueue()
		auxiliary = None
		#  Create first node
		root = TreeNode(num)
		node = root
		#  Add first node into the queue
		q.enQueue(node)
		#  Construct Complete binary tree of K level
		while (k > 1) :
			n = q.isSize()
			while (n > 0) :
				node = q.peek()
				q.deQueue()
				#  Add left node
				node.left = TreeNode(num + 1)
				#  Add right node
				node.right = TreeNode(num + 2)
				#  Add both constructed node into queue
				q.enQueue(node.left)
				q.enQueue(node.right)
				#  Update counter value
				num += 2
				n -= 1
			
			#  Reduce size
			k -= 1
		
		#  Construct bottom part of diamond tree
		while (q.isSize() > 1) :
			#  Get first node
			node = q.peek()
			q.deQueue()
			#  Get second node
			auxiliary = q.peek()
			q.deQueue()
			#  Construct new node and append right side of first node
			node.right = TreeNode(node.key + auxiliary.key)
			#  Connect new node with left of second node
			auxiliary.left = node.right
			#  Add constructor node into queue
			q.enQueue(node.right)
		
		return root
	
	#  Level order traversal in given diamond tree
	def printTree(self, root) :
		q = MyQueue()
		#  Insert first node of queue
		q.enQueue(root)
		n = 0
		#  Define some auxiliary variable
		node = None
		back = root
		#  Print diamond tree element in level order
		while (q.isSize() > 0) :
			#  Get current queue size
			n = q.isSize()
			while (n > 0) :
				node = q.peek()
				#  Remove front node of queue 
				q.deQueue()
				if (node.left != None and node.left != back) :
					back = node.left
					q.enQueue(back)
				
				if (node.right != None and node.right != back) :
					back = node.right
					q.enQueue(back)
				
				#  Display level node
				print(" ", node.key, end = "")
				#  Reduce size
				n -= 1
			
			#  When change level
			print(end = "\n")
		
	

def main() :
	k = 4
	tree = DiamondTree()
	tree.root = tree.constructTree(k)
	tree.printTree(tree.root)

if __name__ == "__main__": main()

Output

  1
  2  3
  4  5  6  7
  8  9  10  11  12  13  14  15
  17  21  25  29
  38  54
  92
#  Ruby Program 
#  Construct Diamond Tree

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

end

#  Queue Node
class QNode  
	# Define the accessor and reader of class QNode  
	attr_reader :n, :next
	attr_accessor :n, :next
 
	
	def initialize(n) 
		self.n = n
		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(n) 
		node = QNode.new(n)
		if (self.front == nil) 
			#  When first node of queue
			self.front = node
		else 
			#  Add node at last position
			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 peek() 
		if (self.isSize() == 0) 
			return nil
		else 
			return self.front.n
		end

	end

end

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

	#  Construct diamond tree 
	def constructTree(k) 
		if (k <= 0) 
			return nil
		end

		#  Define some counter variables
		num = 1
		n = 0
		#  Construct a queue
		q = MyQueue.new()
		auxiliary = nil
		#  Create first node
		root = TreeNode.new(num)
		node = root
		#  Add first node into the queue
		q.enQueue(node)
		#  Construct Complete binary tree of K level
		while (k > 1) 
			n = q.isSize()
			while (n > 0) 
				node = q.peek()
				q.deQueue()
				#  Add left node
				node.left = TreeNode.new(num + 1)
				#  Add right node
				node.right = TreeNode.new(num + 2)
				#  Add both constructed node into queue
				q.enQueue(node.left)
				q.enQueue(node.right)
				#  Update counter value
				num += 2
				n -= 1
			end

			#  Reduce size
			k -= 1
		end

		#  Construct bottom part of diamond tree
		while (q.isSize() > 1) 
			#  Get first node
			node = q.peek()
			q.deQueue()
			#  Get second node
			auxiliary = q.peek()
			q.deQueue()
			#  Construct new node and append right side of first node
			node.right = TreeNode.new(node.key + auxiliary.key)
			#  Connect new node with left of second node
			auxiliary.left = node.right
			#  Add constructor node into queue
			q.enQueue(node.right)
		end

		return root
	end

	#  Level order traversal in given diamond tree
	def printTree(root) 
		q = MyQueue.new()
		#  Insert first node of queue
		q.enQueue(root)
		n = 0
		#  Define some auxiliary variable
		node = nil
		back = root
		#  Print diamond tree element in level order
		while (q.isSize() > 0) 
			#  Get current queue size
			n = q.isSize()
			while (n > 0) 
				node = q.peek()
				#  Remove front node of queue 
				q.deQueue()
				if (node.left != nil && node.left != back) 
					back = node.left
					q.enQueue(back)
				end

				if (node.right != nil && node.right != back) 
					back = node.right
					q.enQueue(back)
				end

				#  Display level node
				print(" ", node.key)
				#  Reduce size
				n -= 1
			end

			#  When change level
			print("\n")
		end

	end

end

def main() 
	k = 4
	tree = DiamondTree.new()
	tree.root = tree.constructTree(k)
	tree.printTree(tree.root)
end

main()

Output

 1
 2 3
 4 5 6 7
 8 9 10 11 12 13 14 15
 17 21 25 29
 38 54
 92
/*
    Scala Program 
    Construct Diamond Tree
*/
// Binary Tree node
class TreeNode(var key: Int , var left: TreeNode , var right: TreeNode)
{
	def this(key: Int)
	{
		this(key, null, null);
	}
}
// Queue Node
class QNode(var n: TreeNode , var next: QNode)
{
	def this(n: TreeNode)
	{
		this(n, 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(n: TreeNode): Unit = {
		var node: QNode = new QNode(n);
		if (this.front == null)
		{
			// When first node of queue
			this.front = node;
		}
		else
		{
			// Add node at last position
			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 peek(): TreeNode = {
		if (this.isSize() == 0)
		{
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
}
class DiamondTree(var root: TreeNode)
{
	def this()
	{
		this(null);
	}
	// Construct diamond tree
	def constructTree(k: Int): TreeNode = {
      
		if (k <= 0)
		{
			return null;
		}
      	var k1 = k;
		// Define some counter variables
		var num: Int = 1;
		var n: Int = 0;
		// Construct a queue
		var q: MyQueue = new MyQueue();
		var auxiliary: TreeNode = null;
		// Create first node
		var root: TreeNode = new TreeNode(num);
		var node: TreeNode = root;
		// Add first node into the queue
		q.enQueue(node);
		// Construct Complete binary tree of K level
		while (k1 > 1)
		{
			// Reduce size
			n = q.isSize();
			while (n > 0)
			{
				node = q.peek();
				q.deQueue();
				// Add left node
				node.left = new TreeNode(num + 1);
				// Add right node
				node.right = new TreeNode(num + 2);
				// Add both constructed node into queue
				q.enQueue(node.left);
				q.enQueue(node.right);
				// Update counter value
				num += 2;
				n -= 1;
			}
			k1 -= 1;
		}
		// Construct bottom part of diamond tree
		while (q.isSize() > 1)
		{
			// Get first node
			node = q.peek();
			q.deQueue();
			// Get second node
			auxiliary = q.peek();
			q.deQueue();
			// Construct new node and append right side of first node
			node.right = new TreeNode(node.key + auxiliary.key);
			// Connect new node with left of second node
			auxiliary.left = node.right;
			// Add constructor node into queue
			q.enQueue(node.right);
		}
		return root;
	}
	// Level order traversal in given diamond tree
	def printTree(root: TreeNode): Unit = {
		var q: MyQueue = new MyQueue();
		// Insert first node of queue
		q.enQueue(root);
		var n: Int = 0;
		// Define some auxiliary variable
		var node: TreeNode = null;
		var back: TreeNode = root;
		// Print diamond tree element in level order
		while (q.isSize() > 0)
		{
			// Get current queue size
			n = q.isSize();
			while (n > 0)
			{
				// Reduce size
				node = q.peek();
				// Remove front node of queue
				q.deQueue();
				if (node.left != null && node.left != back)
				{
					back = node.left;
					q.enQueue(back);
				}
				if (node.right != null && node.right != back)
				{
					back = node.right;
					q.enQueue(back);
				}
				// Display level node
				print(" " + node.key);
				n -= 1;
			}
			// When change level
			print("\n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var k: Int = 4;
		var tree: DiamondTree = new DiamondTree();
		tree.root = tree.constructTree(k);
		tree.printTree(tree.root);
	}
}

Output

 1
 2 3
 4 5 6 7
 8 9 10 11 12 13 14 15
 17 21 25 29
 38 54
 92
/*
    Swift 4 Program 
    Construct Diamond Tree
*/
// Binary Tree node
class TreeNode
{
	var key: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ key: Int)
	{
		// Set node value
		self.key = key;
		self.left = nil;
		self.right = nil;
	}
}
// Queue Node
class QNode
{
	var n: TreeNode? ;
	var next: QNode? ;
	init(_ n: TreeNode? )
	{
		self.n = n;
		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(_ n: TreeNode? )
	{
		let node: QNode? = QNode(n);
		if (self.front == nil)
		{
			// When first node of queue
			self.front = node;
		}
		else
		{
			// Add node at last position
			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 peek()->TreeNode?
	{
		if (self.isSize() == 0)
		{
			return nil;
		}
		else
		{
			return self.front!.n;
		}
	}
}
class DiamondTree
{
	var root: TreeNode? ;
	init()
	{
		// Set root of tree
		self.root = nil;
	}
	// Construct diamond tree
	func constructTree(_ k: Int)->TreeNode?
	{
		if (k <= 0)
		{
			return nil;
		}
      	var k1 = k;
		// Define some counter variables
		var num: Int = 1;
		var n: Int = 0;
		// Construct a queue
		let q: MyQueue = MyQueue();
		var auxiliary: TreeNode? = nil;
		// Create first node
		let root: TreeNode? = TreeNode(num);
		var node: TreeNode? = root;
		// Add first node into the queue
		q.enQueue(node);
		// Construct Complete binary tree of K level
		while (k1 > 1)
		{
			// Reduce size
			n = q.isSize();
			while (n > 0)
			{
				node = q.peek();
				q.deQueue();
				// Add left node
				node!.left = TreeNode(num + 1);
				// Add right node
				node!.right = TreeNode(num + 2);
				// Add both constructed node into queue
				q.enQueue(node!.left);
				q.enQueue(node!.right);
				// Update counter value
				num += 2;
				n -= 1;
			}
			k1 -= 1;
		}
		// Construct bottom part of diamond tree
		while (q.isSize() > 1)
		{
			// Get first node
			node = q.peek();
			q.deQueue();
			// Get second node
			auxiliary = q.peek();
			q.deQueue();
			// Construct new node and append right side of first node
			node!.right = TreeNode(node!.key + auxiliary!.key);
			// Connect new node with left of second node
			auxiliary!.left = node!.right;
			// Add constructor node into queue
			q.enQueue(node!.right);
		}
		return root;
	}
	// Level order traversal in given diamond tree
	func printTree(_ root: TreeNode? )
	{
		let q: MyQueue = MyQueue();
		// Insert first node of queue
		q.enQueue(root);
		var n: Int = 0;
		// Define some auxiliary variable
		var node: TreeNode? = nil;
		var back: TreeNode? = root;
		// Print diamond tree element in level order
		while (q.isSize() > 0)
		{
			// Get current queue size
			n = q.isSize();
			while (n > 0)
			{
				// Reduce size
				node = q.peek();
				// Remove front node of queue
				q.deQueue();
				if (node!.left  != nil && !(node!.left === back))
				{
					back = node!.left;
					q.enQueue(back);
				}
				if (node!.right  != nil && !(node!.right  === back))
				{
					back = node!.right;
					q.enQueue(back);
				}
				// Display level node
				print(" ", node!.key, terminator: "");
				n -= 1;
			}
			// When change level
			print(terminator: "\n");
		}
	}
}
func main()
{
	let k: Int = 4;
	let tree: DiamondTree = DiamondTree();
	tree.root = tree.constructTree(k);
	tree.printTree(tree.root);
}
main();

Output

  1
  2  3
  4  5  6  7
  8  9  10  11  12  13  14  15
  17  21  25  29
  38  54
  92
/*
    Kotlin Program 
    Construct Diamond Tree
*/
// Binary Tree node
class TreeNode
{
	var key: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(key: Int)
	{
		// Set node value
		this.key = key;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
class QNode
{
	var n: TreeNode ? ;
	var next: QNode ? ;
	constructor(n: TreeNode ? )
	{
		this.n = n;
		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(n: TreeNode ? ): Unit
	{
		var node: QNode ? = QNode(n);
		if (this.front == null)
		{
			// When first node of queue
			this.front = node;
		}
		else
		{
			// Add node at last position
			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 peek(): TreeNode ?
	{
		if (this.isSize() == 0)
		{
			return null;
		}
		else
		{
			return this.front?.n;
		}
	}
}
class DiamondTree
{
	var root: TreeNode ? ;
	constructor()
	{
		// Set root of tree
		this.root = null;
	}
	// Construct diamond tree
	fun constructTree(k: Int): TreeNode ?
	{
		if (k <= 0)
		{
			return null;
		}
      	var k1 = k;
		// Define some counter variables
		var num: Int = 1;
		var n: Int ;
		// Construct a queue
		var q: MyQueue = MyQueue();
		var auxiliary: TreeNode ? ;
		// Create first node
		var root: TreeNode = TreeNode(num);
		var node: TreeNode ? = root;
		// Add first node into the queue
		q.enQueue(node);
		// Construct Complete binary tree of K level
		while (k1 > 1)
		{
			// Reduce size
			n = q.isSize();
			while (n > 0)
			{
				node = q.peek();
				q.deQueue();
				// Add left node
				node?.left = TreeNode(num + 1);
				// Add right node
				node?.right = TreeNode(num + 2);
				// Add both constructed node into queue
				q.enQueue(node?.left);
				q.enQueue(node?.right);
				// Update counter value
				num += 2;
				n -= 1;
			}
			k1 -= 1;
		}
		// Construct bottom part of diamond tree
		while (q.isSize() > 1)
		{
			// Get first node
			node = q.peek();
			q.deQueue();
			// Get second node
			auxiliary = q.peek();
			q.deQueue();
			// Construct new node and append right side of first node
			node?.right = TreeNode(node!!.key + auxiliary!!.key);
			// Connect new node with left of second node
			auxiliary.left = node.right;
			// Add constructor node into queue
			q.enQueue(node.right);
		}
		return root;
	}
	// Level order traversal in given diamond tree
	fun printTree(root: TreeNode ? ): Unit
	{
		var q: MyQueue = MyQueue();
		// Insert first node of queue
		q.enQueue(root);
		var n: Int ;
		// Define some auxiliary variable
		var node: TreeNode ? ;
		var back: TreeNode ? = root;
		// Print diamond tree element in level order
		while (q.isSize() > 0)
		{
			// Get current queue size
			n = q.isSize();
			while (n > 0)
			{
				// Reduce size
				node = q.peek();
				// Remove front node of queue
				q.deQueue();
				if (node != null && node.left != null && node.left != back)
				{
					back = node.left;
					q.enQueue(back);
				}
				if (node != null &&  node.right != null && node.right != back)
				{
					back = node.right;
					q.enQueue(back);
				}
				// Display level node
				print(" " + node!!.key);
				n -= 1;
			}
			// When change level
			print("\n");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var k: Int = 4;
	var tree: DiamondTree = DiamondTree();
	tree.root = tree.constructTree(k);
	tree.printTree(tree.root);
}

Output

 1
 2 3
 4 5 6 7
 8 9 10 11 12 13 14 15
 17 21 25 29
 38 54
 92


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