Binary Search Tree in GoLang

bst.go

package main

import "fmt"
import "strconv"

//------------------------------------------------------------------------------

type Node struct {

  data  int
  left  *Node
  right *Node
}

//------------------------------------------------------------------------------

type BST struct {

  size int
  root *Node
}

//------------------------------------------------------------------------------

func (tree *BST) insert(data int) {

  tree.root = tree.add(data, tree.root)
}

//------------------------------------------------------------------------------

func (tree *BST) add(data int, node *Node) *Node {

  if (node == nil) {

    tree.size++

    return &Node{data : data}
  }

  if (data < node.data) {

    node.left = tree.add(data, node.left)

  } else if (data > node.data) {

    node.right = tree.add(data, node.right)
  }

  return node
}

//------------------------------------------------------------------------------

func (tree *BST) remove(data int) {

  tree.root = tree.delete(data, tree.root)
}

//------------------------------------------------------------------------------

func (tree *BST) delete(data int, node *Node) *Node {

  if (node == nil) {

    return nil
  }

  if (data < node.data) {

    node.left = tree.delete(data, node.left)

  } else if (data > node.data) {

    node.right = tree.delete(data, node.right)

  } else {

    if (node.left != nil && node.right != nil) {

      min       := tree.min(node.right)
      node.data  = min.data
      node.right = tree.delete(min.data, node.right)

    } else {

      if (node.left == nil && node.right == nil) {

        node = nil

      } else if (node.left == nil) {

        node = node.right

      } else {

        node = node.left
      }

      tree.size--
    }
  }


  return node
}

//------------------------------------------------------------------------------

  func (tree *BST) min(node *Node) *Node {

    for (node.left != nil) {

      node = node.left
    }

    return node
  }

//------------------------------------------------------------------------------

func (tree BST) inorder() {

  inorder := tree.in(tree.root, "inorder: ")

  fmt.Println(inorder)
}

//------------------------------------------------------------------------------

func (tree BST) in(node *Node, str string) string {

  if (node != nil) {
    str = tree.in(node.left, str)
    str = str + strconv.Itoa(node.data) + " "
    str = tree.in(node.right, str)
  }

  return str
}

//------------------------------------------------------------------------------

func (tree BST) preorder() {

  preorder := tree.pre(tree.root, "preorder: ")

  fmt.Println(preorder)
}

//------------------------------------------------------------------------------

func (tree BST) pre(node *Node, str string) string {

  if (node != nil) {
    str = str + strconv.Itoa(node.data) + " "
    str = tree.pre(node.left, str)
    str = tree.pre(node.right, str)
  }

  return str
}

//------------------------------------------------------------------------------

func (tree BST) postorder() {

  postorder := tree.post(tree.root, "postorder: ")

  fmt.Println(postorder)
}

//------------------------------------------------------------------------------

func (tree BST) post(node *Node, str string) string {

  if (node != nil) {
    str = tree.post(node.left, str)
    str = tree.post(node.right, str)
    str = str + strconv.Itoa(node.data) + " "
  }

  return str
}

//------------------------------------------------------------------------------

func (tree BST) display() {
  fmt.Println("size", tree.size)

  tree.preorder()
  tree.inorder()
  tree.postorder()
  tree.treeString()
}

//------------------------------------------------------------------------------

func (tree BST) treeString() {

  str := tree.toTreeString("", true, "", tree.root)

  fmt.Println(str)
}

//------------------------------------------------------------------------------

func (tree BST) toTreeString(prefix string, top bool, str string, node *Node) string {

  left  := new(Node)
  right := new(Node)

  if (node == nil) {

    return ""
  }

  left  = node.left
  right = node.right

  if (right != nil) {

    temp := tree.path(top, "" + prefix, "│   ", "    ");
    str   = tree.toTreeString(temp, false, str, right);
  }

  str = tree.path(top, str + prefix, "└──", "┌──");
  str = str + " " + strconv.Itoa(node.data) + "\n";

  if (left != nil) {

    temp := tree.path(top, "" + prefix, "    ", "│   ");
    str  = tree.toTreeString(temp, true, str, left);
  }

  return str
}

//------------------------------------------------------------------------------

func (tree BST) path(condition bool, str string, choice1 string, choice2 string) string{

  if (condition) {

    str += choice1;

  } else {

    str += choice2;
  }

  return str;
}

main.go

package main

import "fmt"

func main() {

  tree := &BST{}

  elements := [7]int {50, 30, 20, 40, 70, 60, 80}

  for _, element := range elements {

    tree.insert(element)
  }

  fmt.Println("Elements:", elements)

  tree.display()
}

/*

# To run
go run main.go bst.go

Elements: [50 30 20 40 70 60 80]
size 7
preorder: 50 30 20 40 70 60 80
inorder: 20 30 40 50 60 70 80
postorder: 20 40 30 60 80 70 50
│       ┌── 80
│   ┌── 70
│   │   └── 60
└── 50
    │   ┌── 40
    └── 30
        └── 20
 */