How to format this code?

[JOhn_Stuart (Les Way)]

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 ?

[johandalabacka (Johan Dahl)]

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