package main

import (
	"container/list"
	"fmt"
)

type Node struct {
	Key   int
	Left  *Node
	Right *Node
}

type BinarySearchTree struct {
	Root *Node
}

func (tree *BinarySearchTree) Insert(key int) {
	newNode := &Node{Key: key}

	if tree.Root == nil {
		tree.Root = newNode
		return
	}

	current := tree.Root
	for {
		if key < current.Key {
			if current.Left == nil {
				current.Left = newNode
				return
			}
			current = current.Left
		} else {
			if current.Right == nil {
				current.Right = newNode
				return
			}
			current = current.Right
		}
	}
}

func (tree *BinarySearchTree) BFS() []int {
	result := []int{}
	if tree.Root == nil {
		return result
	}
	queue := list.New()
	queue.PushBack(tree.Root)

	for queue.Len() > 0 {
		node := queue.Remove(queue.Front()).(*Node)
		result = append(result, node.Key)
		if node.Left != nil {
			queue.PushBack(node.Left)
		}
		if node.Right != nil {
			queue.PushBack(node.Right)
		}
	}
	return result
}

func (tree *BinarySearchTree) BFSRecursive() []int {
	result := []int{}
	if tree.Root == nil {
		return result
	}
	queue := list.New()
	queue.PushBack(tree.Root)
	return tree.bfsrec(queue, result)
}

func (tree *BinarySearchTree) bfsrec(queue *list.List, result []int) []int {
	if queue.Len() == 0 {
		return result
	}

	node := queue.Remove(queue.Front()).(*Node)
	result = append(result, node.Key)

	if node.Left != nil {
		queue.PushBack(node.Left)
	}
	if node.Right != nil {
		queue.PushBack(node.Right)
	}

	return tree.bfsrec(queue, result)
}
func main() {
	bst := BinarySearchTree{}

	bst.Insert(50)
	bst.Insert(30)
	bst.Insert(70)
	bst.Insert(20)
	bst.Insert(40)
	bst.Insert(60)
	bst.Insert(80)

	fmt.Println("Breadth-First Search:")
	fmt.Println(bst.BFS())          // Should print [50 30 70 20 40 60 80]
	fmt.Println(bst.BFSRecursive()) // Should print [50 30 70 20 40 60 80]
}