Mastering Recursion with a Tertiary Search Tree: A Hands-On INFS2200/7903 Tutorial

Introduction: Why Recursion Matters in 2026

Recursion is a fundamental programming concept that appears everywhere—from traversing file systems to powering AI recommendation engines. In 2026, as large language models and game AI rely on recursive search algorithms, mastering recursion gives you an edge. This tutorial walks you through implementing a Tertiary Search Tree (TST), a data structure similar to a Binary Search Tree but with three children per node. You'll practice recursion by writing methods for the TSTNode and TST classes, exactly as required in the INFS2200/7903 Project Assignment.

What is a Tertiary Search Tree (TST)?

A TST is a tree where each node stores a comparable element and has three children: left, middle, and right. The left subtree contains elements less than the node's element, the middle subtree contains elements equal to it, and the right subtree contains elements greater than it. This structure is useful for handling duplicates efficiently and can be seen as a generalization of BST. Think of it like a tournament bracket in eSports: each match (node) splits players into three groups—losers (left), tie (middle), winners (right).

Getting Started: The TSTNode Class

The TSTNode class has four fields: an element of type T (which implements Comparable), and three children: left, middle, and right. You'll implement a constructor and three recursive methods.

Constructor: TSTNode(T element)

This assigns the given element to the node and initializes children to null. Simple enough.

public TSTNode(T element) {
    this.element = element;
    this.left = null;
    this.middle = null;
    this.right = null;
}

Method: height()

Returns the height of the subtree rooted at this node. The height is the number of edges on the longest path from this node to a leaf. Use recursion: height = 1 + max(height of left, middle, right children). If the node is a leaf (all children null), height = 0.

public int height() {
    int leftH = (left == null) ? -1 : left.height();
    int midH = (middle == null) ? -1 : middle.height();
    int rightH = (right == null) ? -1 : right.height();
    return 1 + Math.max(leftH, Math.max(midH, rightH));
}

Note: Some definitions use height of a single node as 0; adjust accordingly. Always test with your provided examples.

Method: findMin()

Returns the node with the minimum element in the subtree. Since the left child contains smaller elements, recursively go left until you can't. If left is null, this node is the minimum.

public TSTNode<T> findMin() {
    if (left == null) return this;
    return left.findMin();
}

Method: findMax()

Similar to findMin, but go right.

public TSTNode<T> findMax() {
    if (right == null) return this;
    return right.findMax();
}

These helper methods will be used in the TST class.

The TST Class: Building the Tree

The TST class has a single field: root of type TSTNode<T>. You are given height() and toString() methods. Your task is to implement add(), contains(), and other methods as per assignment. Let's focus on the recursive core.

Method: add(T element)

Insert an element into the TST. Recursively traverse: if element is less than current, go left; if equal, go middle; if greater, go right. When you reach a null child, insert a new node there.

public void add(T element) {
    root = add(root, element);
}

private TSTNode<T> add(TSTNode<T> node, T element) {
    if (node == null) return new TSTNode<>(element);
    int cmp = element.compareTo(node.element);
    if (cmp < 0) node.left = add(node.left, element);
    else if (cmp == 0) node.middle = add(node.middle, element);
    else node.right = add(node.right, element);
    return node;
}

Method: contains(T element)

Check if an element exists in the tree. Recursively compare and follow the appropriate child.

public boolean contains(T element) {
    return contains(root, element);
}

private boolean contains(TSTNode<T> node, T element) {
    if (node == null) return false;
    int cmp = element.compareTo(node.element);
    if (cmp < 0) return contains(node.left, element);
    else if (cmp == 0) return true;
    else return contains(node.right, element);
}

Real-World Analogies: AI and Gaming

Imagine you're building a recommendation system for a streaming platform like Netflix. The TST can store user preferences: less popular (left), average (middle), trending (right). Recursive traversal finds the best match quickly. In gaming, a TST could represent a skill tree where left is weaker skills, middle is equal, right is stronger—recursion helps calculate the height of the skill tree.

Testing Your Code

The assignment provides exposed tests worth 59/100. For the remaining 41 points, you must create your own tests. Think edge cases: empty tree, single node, duplicates, large data sets. Use the provided toString() to visualize your tree. Share test cases on the discussion board—but never share solution code.

Common Pitfalls and Tips

• NullPointerException: Always check for null before accessing children.
• Infinite recursion: Ensure your base case is correct. For height(), base case returns -1 or 0 appropriately.
• Duplicate handling: In TST, duplicates go to the middle child. Make sure your add and contains handle compareTo() == 0 correctly.
• Recursion depth: For very deep trees, recursion may cause stack overflow. But for assignment purposes, it's fine.

Conclusion

By implementing a Tertiary Search Tree, you've practiced recursion in a practical context. This skill translates directly to advanced topics like AI search algorithms, game development, and data analysis. In 2026, as AI assistants like ChatGPT rely on recursive neural networks, understanding recursion is more relevant than ever. Good luck with your INFS2200/7903 assignment—and remember to start early and test thoroughly!