Trees, MinMax, and Binary Search Trees

When I first learned about trees in computer science, I learned that they look like real upside-down trees. A tree starts with a single root, and from that, its branches extend into smaller parts. These branches are called nodes. Each node connects to other nodes, forming a structure that helps organize data in a clean and logical way.

A tree is useful because it shows relationships between the nodes. There is a clear starting point, the root, and every other piece connects back to it in some way. Instead of storing information in one long list, trees let us break problems into smaller parts. Each branch represents a decision or a possibility. The root node will always be the first node; this is true, but when searching for an element, any node can be made a temporary node! When I began building small projects, I realized that many problems can actually be visualized as a tree. Every time you make a choice in a program, you are creating a new branch.

A type of tree which is used for finding the best decision in a game is called a MinMax Tree. MinMax trees are commonly used in game development to find the best possible move, with the best move receiving a positive score and the worst score receiving a negative score. Imagine a game of tic tac toe, every move creates a new board state. From that board state, there are more possible moves. Each of those leads to even more possibilities. If a branch leads to a win, it receives a positive value. If it leads to a loss, it receives a negative value. The algorithm assumes the opponent will always make the best possible move. Because of that, it chooses the move that guarantees the strongest outcome.

Programming a MinMax tree reminded me of my time in band and leadership. MinMax trees find the best possible decision, and in the band, there are a multitude of things that could happen, and as a leader, I need to make sure I am prepared for anything. An example of this is when I led a sectional. If there are issues with rhythms, then before we practice it over and over again incorrectly, I fix the measure and then move on. Another, bigger example, I saw rain in the distance heading our way, so the other leaders on the team calmed the ensemble and packed everything away quickly. These scenarios are all “changes” to the state of the game, and I am the algorithm searching for the best possible move.

Along with the band, I also wanted to try to implement a MinMax tree in a game I made, Match Master. Match Master is a strategy based game I built, and adding a MinMax tree based AI would allow the computer to play against the user and add another element of excitement. The number of possible moves can grow quickly, and because trees use recursion, this can break my game very fast, but anything is possible.

Another important type of tree is the binary search tree. A binary search tree, or BST, is a tree where each node has at most two children. What makes it special is the rule it follows. For every node, values smaller than it go to the left, and values larger than it go to the right. Because of this structure, searching becomes much faster. Instead of checking every value one by one, you eliminate half the possibilities at each step.

Binary search trees are powerful because they combine structure with efficiency. If I insert the numbers 8, 3, 10, 1, 6, 14 into a BST, the tree organizes itself in a way that makes future searches quick. To find 6, I would start at 8, move left to 3, then right to 6. That process is much faster than scanning through a list.

Trees reflect decision-making. They show how small choices branch into larger outcomes. In programming, they help us build smarter systems. In games, they help us think ahead. In data storage, they help us stay organized.