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