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