Level order traversal using queue in swift

Swift program for Level order traversal using queue. Here problem description and explanation.

import Foundation
/*
  Swift 4 program for
  Level order tree traversal using queue
*/
// Create Q node
class QNode
{
	var data: TreeNode? ;
	var next: QNode? ;
	init(_ node: TreeNode? )
	{
		self.data = node;
		self.next = nil;
	}
}
// 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 MyQueue
{
	var head: QNode? ;
	var tail: QNode? ;
	var count: Int;
	init()
	{
		self.head = nil;
		self.tail = nil;
		self.count = 0;
	}
	func size() -> Int
	{
		return self.count;
	}
	func isEmpty() -> Bool
	{
		return self.count == 0;
	}
	// Add new node of queue
	func enqueue(_ value: TreeNode? )
	{
		// Create a new node
		let node: QNode? = QNode(value);
		if (self.head == nil)
		{
			// Add first element into queue
			self.head = node;
		}
		else
		{
			// Add node at the end using tail
			self.tail!.next = node;
		}
		self.count += 1;
		self.tail = node;
	}
	// Delete a element into queue
	func dequeue()
	{
		if (self.head == nil)
		{
			// Empty Queue
			return;
		}
		// Visit next node
		self.head = self.head!.next;
		self.count -= 1;
		if (self.head == nil)
		{
			// When deleting a last node of linked list
			self.tail = nil;
		}
	}
	// Get front node
	func peek() -> TreeNode?
	{
		if (self.head == nil)
		{
			return nil;
		}
		return self.head!.data;
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	func levelOrder()
	{
		if (self.root  != nil)
		{
			let q: MyQueue? = MyQueue();
			// Add first node
			q!.enqueue(self.root);
			var node: TreeNode? = self.root;
			while (q!.isEmpty() == false && node  != nil)
			{
				if (node!.left  != nil)
				{
					// Add left child node
					q!.enqueue(node!.left);
				}
				if (node!.right  != nil)
				{
					// Add right child node
					q!.enqueue(node!.right);
				}
				// Display level node
				print(node!.data, terminator: "  ");
				// Remove current node
				q!.dequeue();
				// Get new head
				node = q!.peek();
			}
		}
		else
		{
			print("Empty Tree");
		}
	}
	static func main(_ args: [String])
	{
		// Create new tree
		let tree: BinaryTree? = BinaryTree();
		/*
		  Make A Binary Tree
		  -----------------------
		         1
		       /   \
		      2     3
		     /     / \
		    4     5   6
		   /     / \
		  7     8   9
		*/
		// Adding tree nodes
		tree!.root = TreeNode(1);
		tree!.root!.left = TreeNode(2);
		tree!.root!.right = TreeNode(3);
		tree!.root!.right!.right = TreeNode(6);
		tree!.root!.right!.left = TreeNode(5);
		tree!.root!.left!.left = TreeNode(4);
		tree!.root!.left!.left!.left = TreeNode(7);
		tree!.root!.right!.left!.left = TreeNode(8);
		tree!.root!.right!.left!.right = TreeNode(9);
		// Display level order  element
		tree!.levelOrder();
	}
}
BinaryTree.main([String]());

Output

1  2  3  4  5  6  7  8  9



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.

New Comment







© 2022, kalkicode.com, All rights reserved