I've been thinking about how we handle lookups for our server ID registry. Right now, we're just using a slice, and every time we need to check if a specific server ID exists, we're iterating through the whole thing. It's fine for ten servers, but it's a disaster for ten thousand. We need something that cuts the search space in half with every step. Let's try building a Binary Search Tree (BST) from scratch.

Getting the Shape Right

First, I need a way to represent a single point in the tree. In Go, this is a classic case for a struct with pointers to itself. I'll call it a Node. Since we're tracking server IDs, I'll use int.

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

At first glance, this looks simple. But here's where I usually trip up: how do I actually add a node? If I just create a Node and assign it to a variable, I've got a root, but no way to link subsequent nodes without some logic. I can't just append to a list; I have to decide whether the new ID goes to the left or the right based on its value.

The Insertion Struggle

I'll start by writing a simple Insert function. My initial instinct is to make it a standalone function, but then I realize I have to handle the case where the tree is completely empty (the root is nil). If I just pass a pointer to the root, I can't change the root itself inside the function because Go passes pointers by value.

Let's see what happens if I try this:

func Insert(root *Node, id int) {
    if root == nil {
        root = &Node{ID: id}
        return
    }
    // ... logic for left/right
}

I quickly realized that root = &Node{ID: id} only changes the local copy of the pointer. The original root in my main function stays nil. To fix this, I have two choices: use a pointer-to-a-pointer (which is messy) or have the function return the updated node. I'll go with the latter—it's much cleaner and more idiomatic for recursive structures.

func Insert(node *Node, id int) *Node {
    if node == nil {
        return &Node{ID: id}
    }

    if id < node.ID {
        node.Left = Insert(node.Left, id)
    } else if id > node.ID {
        node.Right = Insert(node.Right, id)
    }
    // If id == node.ID, we do nothing (no duplicates in our registry)
    
    return node
}

Now, the recursion handles the traversal. If the ID is smaller, I dive left; if it's larger, I dive right. The return node at the end ensures that as the recursion unwinds, the parent nodes stay connected to their children.

Hunting for a Specific ID

Now that I can put data in, I need to get it out. Searching a BST is where the efficiency comes from. If I'm looking for ID 50 and the root is 100, I can instantly ignore the entire right side of the tree. I'm basically playing a game of "higher or lower" with the data.

func Search(node *Node, id int) bool {
    if node == nil {
        return false
    }

    if id == node.ID {
        return true
    }

    if id < node.ID {
        return Search(node.Left, id)
    }
    return Search(node.Right, id)
}

I like this because it's concise. If I hit nil, the ID isn't there. If I find a match, I'm done. Otherwise, I narrow the search. It's $O(\log n)$ time complexity, which is a massive upgrade over our old slice.

Proving it Actually Works

Here's the problem: if I print the root node, I only see the root and its immediate children. I can't "see" the tree. To verify that my Insert logic is actually maintaining the sorted property, I need to perform an In-Order Traversal. If I visit the left child, then the current node, then the right child, the IDs should come out in perfectly ascending order.

func InOrder(node *Node) {
    if node == nil {
        return
    }
    InOrder(node.Left)
    fmt.Printf("%d ", node.ID)
    InOrder(node.Right)
}

I'll run a quick test with some random server IDs: 50, 30, 20, 40, 70, 60, 80. If the output is 20 30 40 50 60 70 80, I know my pointers are wired correctly. If I see 50 30..., I've messed up the traversal or the insertion logic. In this case, the in-order traversal confirms the BST property is intact.

📋 Practical Task

Build a BST-based Server Health Tracker

You need to extend the Binary Search Tree concept to track not just server IDs, but their current health status. Your task is to implement a system that stores server data and allows for efficient retrieval.

• Modify the Node struct to include a Status string field (e.g., "Healthy", "Warning", "Critical").
• Implement an InsertOrUpdate function: If the ID already exists in the tree, update its Status instead of creating a new node.
• Implement a GetStatus function that returns the status of a specific ID. If the ID is not found, return "Unknown".
• Create a main function that:
  1. Inserts three servers: ID 10 (Healthy), ID 5 (Warning), and ID 15 (Critical).
  2. Updates ID 5 to "Healthy".
  3. Prints the status of ID 5 (should be Healthy) and ID 20 (should be Unknown).