Skip to main content

Level order traversal using queue in golang

Go program for Level order traversal using queue. Here problem description and other solutions.

package main
import "fmt"
/*
  Go program for
  Level order tree traversal using queue
*/
// Create Q node
type QNode struct {
	data * TreeNode
	next * QNode
}
func getQNode(node * TreeNode) * QNode {
	// return new QNode
	return &QNode {
		node,
		nil,
	}
}
// Binary Tree Node
type TreeNode struct {
	data int
	left * TreeNode
	right * TreeNode
}
func getTreeNode(data int) * TreeNode {
	// return new TreeNode
	return &TreeNode {
		data,
		nil,
		nil,
	}
}
type MyQueue struct {
	head * QNode
	tail * QNode
	count int
}
func getMyQueue() * MyQueue {
	// return new MyQueue
	return &MyQueue {
		nil,
		nil,
		0,
	}
}
func(this MyQueue) size() int {
	return this.count
}
func(this MyQueue) isEmpty() bool {
	return this.count == 0
}
// Add new node of queue
func(this *MyQueue) enqueue(value * TreeNode) {
	// Create a new node
	var node * QNode = getQNode(value)
	if this.head == nil {
		// Add first element into queue
		this.head = node
	} else {
		// Add node at the end using tail
		this.tail.next = node
	}
	this.count++
	this.tail = node
}
// Delete a element into queue
func(this *MyQueue) dequeue() {
	if this.head == nil {
		// Empty Queue
		return
	}
	// Visit next node
	this.head = this.head.next
	this.count--
	if this.head == nil {
		// When deleting a last node of linked list
		this.tail = nil
	}
}
// Get front node
func(this MyQueue) peek() * TreeNode {
	if this.head == nil {
		return nil
	}
	return this.head.data
}
type BinaryTree struct {
	root * TreeNode
}
func getBinaryTree() * BinaryTree {
	// return new BinaryTree
	return &BinaryTree {
		nil,
	}
}
func(this BinaryTree) levelOrder() {
	if this.root != nil {
		var q * MyQueue = getMyQueue()
		// Add first node
		q.enqueue(this.root)
		var node * TreeNode = this.root
		for (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
			fmt.Print("  ", node.data)
			// Remove current node
			q.dequeue()
			// Get new head
			node = q.peek()
		}
	} else {
		fmt.Println("Empty Tree")
	}
}
func main() {
	// Create new tree
	var tree * BinaryTree = getBinaryTree()
	/*
	  Make A Binary Tree
	  -----------------------
	         1
	       /   \
	      2     3
	     /     / \
	    4     5   6
	   /     / \
	  7     8   9
	*/
	// Adding tree nodes
	tree.root = getTreeNode(1)
	tree.root.left = getTreeNode(2)
	tree.root.right = getTreeNode(3)
	tree.root.right.right = getTreeNode(6)
	tree.root.right.left = getTreeNode(5)
	tree.root.left.left = getTreeNode(4)
	tree.root.left.left.left = getTreeNode(7)
	tree.root.right.left.left = getTreeNode(8)
	tree.root.right.left.right = getTreeNode(9)
	// Display level order  element
	tree.levelOrder()
}

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