Skip to content

Instantly share code, notes, and snippets.

@fogonthedowns
Last active April 15, 2020 19:18
Show Gist options
  • Save fogonthedowns/4ad654432bc1ac4e881a04d97059160b to your computer and use it in GitHub Desktop.
Save fogonthedowns/4ad654432bc1ac4e881a04d97059160b to your computer and use it in GitHub Desktop.
Height Of Binary Tree in Go
package main
import (
"fmt"
)
type Node struct {
Value int
Left *Node
Right *Node
}
type NodeInit map[int][]int
func main() {
// data source
// index mapped to meaningless number, index of left child, index of right child
// -1 means no child
ds := make(NodeInit, 0)
ds[0] = []int{1, -1, -1}
ds[1] = []int{3, -1, -1}
ds[2] = []int{2, 0, 1}
ds[3] = []int{6, -1, -1}
ds[4] = []int{4, 2, 3}
ds[5] = []int{1, -1, 4}
fmt.Println(ds)
nodes := createNodes(ds)
last := nodes[len(nodes)-1]
fmt.Println(height(&last))
}
func createNodes(n NodeInit) (nodes []Node) {
for i := 0; i < len(n); i++ {
node := Node{}
nodes = append(nodes, node)
}
for idx, _ := range n {
nodes[idx].Value = n[idx][0]
if n[idx][1] == -1 {
nodes[idx].Left = nil
} else {
nodes[idx].Left = &nodes[n[idx][1]]
}
if n[idx][2] == -1 {
nodes[idx].Right = nil
} else {
nodes[idx].Right = &nodes[n[idx][2]]
}
}
return nodes
}
func height(n *Node) int {
if n == nil {
return 0
}
leftHeight := height(n.Left)
rightHeight := height(n.Right)
if leftHeight > rightHeight {
return leftHeight + 1
} else {
return rightHeight + 1
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment