It is quite easy but not so elegant to walk the tree with a while loop until a randomly selected branch is null and then add a new node to its parent (in the correct branch left/right previous taken. Faster but recursion is nice and often makes quite beautiful algorithms
https://play.golang.org/p/KqbGptCtaWg
package main
import (
"fmt"
"math/rand"
)
type binaryTree struct {
head *node
}
type node struct {
value interface{}
left *node
right *node
}
func (b binaryTree) String() string {
return fmt.Sprintf("(%v %v %v)", b.head.value, b.head.left, b.head.right)
}
func (n node) String() string {
if n.left == nil && n.right == nil {
return fmt.Sprintf("(%v)", n.value)
}
return fmt.Sprintf("(%v %v %v)", n.value, n.left, n.right)
}
func (b *binaryTree) Add(value interface{}) {
if b.head == nil {
b.head = &node{value: value, left: nil, right: nil}
return
}
addRecursive(b.head, value)
}
func (b *binaryTree) AddNonRecursive(value interface{}) {
if b.head == nil {
b.head = &node{value: value, left: nil, right: nil}
return
}
var parent *node
current := b.head
var left bool
for current != nil {
parent = current
left = rand.Intn(2) == 0
if left {
current = current.left
} else {
current = current.right
}
}
new := &node{value: value, left: nil, right: nil}
if left {
parent.left = new
} else {
parent.right = new
}
}
func addRecursive(n *node, val interface{}) *node {
if n == nil {
n = &node{value: val, left: nil, right: nil}
return n
}
left := rand.Intn(2) == 0
if left {
n.left = addRecursive(n.left, val)
} else {
n.right = addRecursive(n.right, val)
}
return n
}
func main() {
rand.Seed(77)
tree1 := binaryTree{}
for i := 1; i < 10; i++ {
tree1.Add(i)
}
fmt.Println(tree1)
rand.Seed(77)
tree2 := binaryTree{}
for i := 1; i < 10; i++ {
tree2.AddNonRecursive(i)
}
fmt.Println(tree2)
}