tree.go (1177B)
1 package dsa 2 3 type Node struct { 4 value *int 5 left *Node 6 right *Node 7 } 8 9 type Tree struct { 10 n *Node 11 } 12 13 // Insert places the element in the first available slot. 14 func (t *Tree) Insert(elem int) { 15 newNode := &Node{value: &elem} 16 if t.n == nil { 17 t.n = newNode 18 return 19 } 20 21 parent := t.Bfs(nil) // Find the parent node to insert the new node 22 if parent != nil { 23 if parent.left == nil { 24 parent.left = newNode 25 } else if parent.right == nil { 26 parent.right = newNode 27 } 28 } 29 } 30 31 // Bfs performs a breadth-first search to find a node with an available slot. 32 func (t *Tree) Bfs(target *int) *Node { 33 var q Queue 34 q.Enqueue(t.n) // Enqueue the root node 35 36 for !q.IsEmpty() { 37 38 currentInterface, _ := q.Dequeue() 39 current, ok := currentInterface.(*Node) 40 41 if !ok { 42 return nil 43 } 44 45 // Return this node if it has space for a new child 46 if current.left == nil || current.right == nil { 47 return current 48 } 49 50 // Otherwise, enqueue its children to continue the search 51 if current.left != nil { 52 q.Enqueue(current.left) 53 } 54 if current.right != nil { 55 q.Enqueue(current.right) 56 } 57 } 58 59 return nil // Return nil if no suitable parent is found (should not happen) 60 }