/*
	Binary Search Tree GoLang
	Rupal barman
	rupalbarman@gmail.com
*/

package main

import (
	"fmt"
	"math/rand"
)


type Tree struct {
	Left  *Tree
	Value int
	Right *Tree
}


func New(n, k int) *Tree {
	var t *Tree
	for _, v := range rand.Perm(n) {
		t = insert(t, v)
	}
	return t
}

func insert(t *Tree, v int) *Tree {
	if t == nil {
		return &Tree{nil, v, nil}
	}
	if v < t.Value {
		t.Left = insert(t.Left, v)
		return t
	}
	t.Right = insert(t.Right, v)
	return t
}

func inorder(t *Tree) {
  if t!=nil{
    inorder(t.Left)
    fmt.Println(t.Value)
    inorder(t.Right)
  }
}

func preorder(t *Tree) {
  if t!=nil{
    preorder(t.Left)
    preorder(t.Right)
    fmt.Println(t.Value)
  }
}

func main() {
	t := New(10, 1)
	fmt.Println("Preorder")
	preorder(t)
	fmt.Println("Inorder")
	inorder(t)
}