gabrielbussolo · September 14, 2023 10:56 · Sep 14, 2023
diff --git a/bfs.go b/bfs.go
@@ -0,0 +1,106 @@
+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]
+}