How do I structure the Node so Swift doesn't complain about optionality?

When you're building a BST, the biggest hurdle for a lot of Swift developers is the recursive nature of the nodes. Since a node might not have a left or right child, those properties must be optionals. I always recommend using a class here rather than a struct. Why? Because trees are inherently reference-based. If you use a struct, you'll run into a nightmare of mutating copies every time you try to move down a level.

Let's say we're building a system to track Book IDs in a library. Here is how I'd set up the basic node:

class BSTNode {
    var value: Int
    var left: BSTNode?
    var right: BSTNode?

    init(value: Int) {
        self.value = value
    }
}

Notice that left and right are BSTNode?. This is key. It allows the leaf nodes to simply be nil, which is our signal to stop recursing.

What's the most intuitive way to handle insertions?

The logic for insertion is a classic "left or right" decision. If the new value is less than the current node, you head left. If it's greater, you head right. The trick is handling the case where the child is currently nil—that's where the new node actually gets placed.

I prefer wrapping the BSTNode inside a BinarySearchTree class. It keeps the API clean so the user doesn't have to manually track the root node. Here is how I'd implement the insertion logic:

class BinarySearchTree {
    var root: BSTNode?

    func insert(_ value: Int) {
        root = insertRecursive(root, value)
    }

    private func insertRecursive(_ node: BSTNode?, _ value: Int) -> BSTNode {
        // If we've reached a nil spot, we've found the home for the new node
        guard let node = node else {
            return BSTNode(value: value)
        }

        if value < node.value {
            node.left = insertRecursive(node.left, value)
        } else if value > node.value {
            node.right = insertRecursive(node.right, value)
        }
        
        // Return the node to maintain the link to the parent
        return node
    }
}

One little detail: I used else if value > node.value. I'm intentionally ignoring equal values here because standard BSTs usually don't allow duplicates. If you need duplicates, you'd have to decide if they always go right or if you'll add a counter to the node.

How do I actually retrieve a value from the tree efficiently?

This is where the BST really shines. Instead of checking every single element (like you would in an array), you can discard half the tree with every single step. It's the same logic as the insertion, but instead of creating a node, you're just returning a boolean or the node itself.

I like to write the search as a simple recursive helper. It's clean and reads almost like a sentence:

func contains(_ value: Int) -> Bool {
    return searchRecursive(root, value)
}

private func searchRecursive(_ node: BSTNode?, _ value: Int) -> Bool {
    guard let node = node else {
        return false // We hit a leaf and didn't find it
    }

    if value == node.value {
        return true // Found it!
    }

    return value < node.value 
        ? searchRecursive(node.left, value) 
        : searchRecursive(node.right, value)
}

By using the ternary operator here, the code stays compact. You're essentially saying: "If the value is smaller, look left; otherwise, look right."

📋 Practical Task

Exercise: Building a Book ID Validator

Imagine you are managing a digital archive. You have a list of Book IDs that have already been registered: [50, 25, 75, 12, 37, 60, 90].

Your task is to:

• Implement the BinarySearchTree and BSTNode classes as discussed in the lesson.
• Insert the provided list of Book IDs into your tree.
• Write a function called validateBookExists(_ id: Int) that uses your BST search logic to return true if the ID is in the tree and false otherwise.
• Test your implementation by checking for an ID that exists (e.g., 37) and one that doesn't (e.g., 100) and print the results to the console.