Binary Tree Inorder Traversal using Golang with recursion

 In earlier post we see how to create a binary search tree, In this post we going to iterate over BST using inorder traversal. Inorder traversal is a very unique algorithm, if our tree in BST in that case our data is print in sorting order.

Sometimes in interview when interviewer asked that is given tree is BST or not in that case we can give the solution that if we gathered data using inorder traversal and if it is in sorting order in that case our tree is BST.

 

Algorithm:

1. First visit all the left node using recursion.
2. Print the data.
3. Visit all the right node using recursion.

Code:

package main

import "fmt"

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
}

//InOrder print node of tree
func (root *bst) InOrder() {
	if nil == root {
		return
	}
	root.leftNode.InOrder()
	fmt.Printf("%d ", root.rootValue)
	root.rightNode.InOrder()
}

//InOrder print node of tree
func (root *bst) PreOrder() {
	if nil == root {
		return
	}
	fmt.Printf("%d ", root.rootValue)
	root.leftNode.InOrder()
	root.rightNode.InOrder()
}

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
	root.InOrder()
	fmt.Println()
}

 

 

Example of inorder traversal, we have posted other method as well.If you wanted to solve mcq queue based on golang and python, check quiz section, soon we will going to post data structure based quizzes as well.