Level Order Binary Tree Traversal using Golang

We'll use Golang to build level order binary tree traversal in today's blog article. We need an algorithm for level order traversal that goes level by level or depth by depth and prints the number of nodes from each level. We can't utilise inorder, postorder, or preorder traversal for this problem since they employ recursion and work on a stock-based solution; instead, we need an algorithm that works on a queue-based solution.

In this case, breadth first search (BFS) is quite beneficial. In this case, we'll start with the root node and enqueue it, then dequeue and enquue its left side node and right side node the following time. We'll keep repeating this process till the list isn't empty.

 

Below is the steps which we are going to follow for level order traversal:

1. Visit the root node, enqueue the root node.(append in the list)
2. check for its left sub-tree node and right sub-tree node, and push them inside the list.
3. Get first element from the list and check for its left and right side of tree and store into queue.
4. Apply same steps from 1 to 3 till the list is not empty.

 

 Code:

 

package main

import (
	"fmt"
	"time"
)

type bst struct {
	rootValue int
	leftNode  *bst
	rightNode *bst
}

//createNode used to create a node for binary search tree
func createNode(value int) *bst {
	return &bst{
		rootValue: value,
		leftNode:  nil,
		rightNode: nil,
	}
}

func (root *bst) Insert(value int) {
	if value < root.rootValue {
		if root.leftNode == nil {
			root.leftNode = createNode(value)
			return
		}
		root.leftNode.Insert(value)
	}
	if value > root.rootValue {
		if nil == root.rightNode {
			root.rightNode = createNode(value)
			return
		}
		root.rightNode.Insert(value)
	}
	//if its going to equal to root value
	//then we are going to ignore that value
	//we don't want duplicate value
}

func (root *bst) LevelWiseTraversal() {
	nodeList := make([]*bst, 0)
	if nil == root {
		return
	}
	temp := &bst{}
	nodeList = append(nodeList, root)
	for len(nodeList) > 0 {
		temp, nodeList = nodeList[0], nodeList[1:]
		if nil != temp.leftNode {
			//enqueue in the list
			nodeList = append(nodeList, temp.leftNode)
		}
		if nil != temp.rightNode {
			nodeList = append(nodeList, temp.rightNode)
		}
		fmt.Printf("%d\t", temp.rootValue)
		time.Sleep(1 * time.Second)
	}
	fmt.Println()
}

func main() {
	numbers := []int{5, 10, 1, 21, 11, 7, 9}
	var root *bst
	var rootNode bool = true
	for _, value := range numbers {
		if rootNode {
			root = createNode(value)
			rootNode = false
		}
		root.Insert(value)
	}
	//lets print the tree
	
	//levelorder node
	root.LevelWiseTraversal()
}


 

 

We posted other interview question solution as well, feel free to check and let us know in comment if you have any doubt.