# How to format this code?

This is an exercise of a simple binary tree implementation. Here is the code:

https://play.golang.org/p/HWC1BWBMiWs

SO I want to add a new node, randomly in the left subtree or right subtree.

Using this recursion seems wasteful (system stack add a bit of overhead) plus returning the head of every subtree (line 21) is again wasteful.

Otherwise, if I decide to add value in left subtree, I must first check to see if the left subtree is nil and create it, or recurse on it. This retuning of the current subtree head saves a few lines of code, thus making code shorter.

How do you advice me to write this method ?

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 {
}

type node struct {
value interface{}
left *node
right *node
}

func (b binaryTree) String() string {
}
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{}) {
b.head = &node{value: value, left: nil, right: nil}

return
}

}

func (b *binaryTree) AddNonRecursive(value interface{}) {
b.head = &node{value: value, left: nil, right: nil}

return
}
var parent *node
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 {
} else {
}

return n
}

func main() {
rand.Seed(77)
tree1 := binaryTree{}
for i := 1; i < 10; i++ {