struct Node {
	key int

pub mut:
	left &Node
	right &Node
}

fn create_node(key int) &Node {
	node := &Node {
		key: key
	}

	return node
}

fn insert(parent mut Node, key int) &Node {
	if isnil(parent) {
		println('node is null, we have found a spot for $key')
		return create_node(key)
	}

	if key < parent.key {
		println('$key is less than $parent.key, continue left')
		parent.left = insert(mut parent.left, key)
	} else if key > parent.key {
		println('$key is greater than $parent.key, continue right')
		parent.right = insert(mut parent.right, key)
	} else {
		println('$key is equal to $parent.key, default to left')
		parent.left = insert(mut parent.left, key)
	}

	return parent
}

fn inorder(node Node){
	println('inorder traversal')

	if isnil(node){
		println('Reached a null node')
		return
	}

	inorder(node.left)
	println(node.key)
	inorder(node.right)
}

fn main() {
	mut head := create_node(10)
	head = insert(mut head, 9)
	println('')

	head = insert(mut head, 12)
	println('')

	head = insert(mut head, 13)
	println('')

	inorder(head)
}



==== OUTPUT ====
9 is less than 10, continue left
node is null, we have found a spot for 9

12 is greater than 10, continue right
node is null, we have found a spot for 12

13 is greater than 10, continue right
13 is greater than 12, continue right
node is null, we have found a spot for 13

inorder traversal
inorder traversal