Sorted Array To Balanced BST with Golang

May 17, 2017

Development, Golang

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Today we going to learn how we can do it in Go (Golang). Here link in Wikkipedia for those who forgot what is all about. The rest is just a technique 🙂

//Node represent basic entity
type Node struct {
	data        int
	Left, Right *Node
}

// ArrayToBinaryTree transform array to binary tree
func ArrayToBinaryTree(a []int, start int, end int) *Node {
	if start > end {
		var returnNode *Node
		return returnNode
	}

	middle := (start + end) / 2
	node := Node{data: a[middle]}

	node.Left = ArrayToBinaryTree(a, start, middle-1)
	node.Right = ArrayToBinaryTree(a, middle+1, end)

	return &node
}

// PrintPreorder is a utility function to print preorder traversal of BST
func PrintPreorder(node *Node) {
	if node == nil {
		return
	}

	fmt.Println(node.data)

	PrintPreorder(node.Left)
	PrintPreorder(node.Right)
}

Here we call our code from the main function:

func main() {

	a := []int{10, 20, 30, 40, 50, 60, 70, 80, 90}
	node := ArrayToBinaryTree(a, 0, len(a)-1)

	PrintPreorder(node)
}

Output will be : 50 20 10 30 40 70 60 80 90