Binary Search Tree (Go)

package main

/**
 * Project 1: programming in Go lang
 * Using Go Lang, write a program that:
 *    - fills an array with random integers in the range 10 to 99.
 *    - builds a binary search tree by inserting the integers in the array into a tree.
 *    - finds the length of a given BST.
 *    - finds the number of leaf nodes.
 *    - finds the minimum value in a given BST.
 *    - prints the BST in 2D in reverse in-order traversal.
 *    - traverses the tree with pre-order, in-order, and post-order algorithms, printing each value in the tree along the way.
 *
 * author: Nicholas Adamou
 * date: 10/7/19
 * Class: CSC-315
 */

import (
    "fmt"
    "math/rand"
)

type Node struct {
    value int
    left *Node
    right *Node
}

func insert(root *Node, value int) *Node {
    // searching for the place to insert

    if root == nil {
        root = &Node{value, nil, nil}
    } else if value < root.value {               // x is greater. Should be inserted to right
        root.left = insert(root.left, value)
    } else {                                    // x is smaller. Should be inserted to left
        root.right = insert(root.right, value)
    }

    return root
}

// function to find the length of a given BST
func length(root *Node) (count int) {
    if root == nil {
        return 0
    } else {
        return 1 + length(root.left) + length(root.right)
    }
}

// function to find the total number of leaf nodes in a given BST
func getNumberOfLeafNodes(root *Node) (count int) {
    if root == nil {
        return 0
    }

    if root.left == nil && root.right == nil {
        return 1
    } else {
        return getNumberOfLeafNodes(root.left) + getNumberOfLeafNodes(root.right)
    }
}

// function to find the minimum value in a node
func findMinimum(root *Node) *Node {
    if root == nil {
        return nil
    } else if root.left != nil {                // node with minimum value will have no left child
        return findMinimum(root.left)           // left most element will be minimum
    }

    return root
}

// Function to print binary tree in 2D
// It does reverse in-order traversal
func print2DUtil(root *Node, depth int) {
    const COUNT = 4                             // default number of spaces

    if root == nil {                            // base case
        return
    }

    depth += COUNT                              // increase distance between levels

    print2DUtil(root.right, depth)              // process right child first

    // print current Node after space count
    fmt.Printf("\n")
    for i := COUNT; i < depth; i++ {
        fmt.Printf(" ")
    }
    fmt.Printf("%d\n", root.value)

    print2DUtil(root.left, depth)               // process left child last
}

func print2D(root *Node) {
    // pass initial depth as 0
    print2DUtil(root, 0)
}

func preorder(root *Node) {
    if root != nil {                            // checking if the root is not null
        fmt.Printf(" %d ", root.value)          // printing data at root
        preorder(root.left)                     // visiting left child
        preorder(root.right)                    // visiting right child
    }
}

func inorder(root *Node) {
    if root != nil {                            // checking if the root is not null
        inorder(root.left)                      // visiting left child
        fmt.Printf(" %d ", root.value)          // printing data at root
        inorder(root.right)                     // visiting right child
    }
}

func postorder(root *Node) {
    if root != nil {                            // checking if the root is not null
        postorder(root.left)                    // visiting left child
        postorder(root.right)                   // visiting right child
        fmt.Printf(" %d ", root.value)          // printing data at root
    }
}

func main() {
    var n int                                   // random number

    const MIN = 10                              // min number a given node can hold
    const MAX = 99                              // max number a given node can hold
    const SIZE = 10                             // number of nodes in the BST

    var root *Node = &Node{rand.Int() % (MAX - MIN + 1) + MIN, nil, nil}

    for i:= 0; i < SIZE; i++ {
        n = rand.Int() % (MAX - MIN + 1) + MIN

        insert(root, n)
    }

    fmt.Printf("Preorder traversal of BST:\n")
    preorder(root);
    fmt.Printf("\n\n")

    fmt.Printf("Inorder traversal of BST:\n")
    inorder(root);
    fmt.Printf("\n\n")

    fmt.Printf("Postorder traversal of BST:\n")
    postorder(root);
    fmt.Printf("\n\n")

    fmt.Printf("Number of Nodes: %d\n", length(root))
    fmt.Printf("Number of Leaf Nodes: %d\n", getNumberOfLeafNodes(root))
    fmt.Printf("Minimum value: %d\n", findMinimum(root).value)

    print2D(root)
}