Trees, Search Trees, Heaps, and Tries

Introduction and Context

A tree is a non-linear data structure used to represent hierarchical relationships. Unlike an array or linked list, whose elements are commonly arranged along a single sequence, a tree allows one element to have several descendants. File systems, compiler syntax trees, database indexes, organisation charts, web-document object models, decision systems, autocomplete services, and priority queues all use tree-based ideas.

This chapter develops practical foundations for implementing and using binary trees, binary search trees (BSTs), balanced search trees, heaps, and tries in Java and Python. The central design question is: what relationship between stored values should the structure preserve?

• A binary tree preserves parent–child structure but not necessarily ordering.
• A BST preserves an ordering relationship that supports search.
• A balanced tree controls height so operations remain efficient.
• A heap preserves priority near the root.
• A trie preserves prefixes of strings.

The structures are related, but they solve different problems. Selecting the correct one is more important than memorising implementation details.

Learning Objectives

By the end of this chapter, you should be able to:

1. Define tree terminology and represent binary trees.
2. Implement recursive and iterative tree traversals in Java and Python.
3. Construct, search, insert into, and delete from a BST.
4. Analyse tree operations using height and asymptotic complexity.
5. Explain why balanced search trees are needed and describe AVL and red–black ideas.
6. Implement and apply min-heaps and max-heaps.
7. Explain tries and use them for prefix search and autocomplete.
8. Select an appropriate tree structure for indexing, expression processing, hierarchical data, and top-k queries.

1. Tree Foundations

A node stores data and references to zero or more child nodes. A root has no parent. A node with no children is a leaf. The degree of a node is its number of children. A path is a sequence of connected nodes. The depth of a node is the number of edges from the root to that node. The height of a node is the number of edges on the longest downward path from it to a leaf. The height of an empty tree is conventionally −1, while a one-node tree has height 0.

A subtree consists of a node and all its descendants. A binary tree has at most two children per node, conventionally named left and right. A binary tree is full if every node has either zero or two children. It is complete if every level except possibly the last is full and the last level is filled from left to right. It is perfect if all internal nodes have two children and all leaves occur at the same depth.

For a perfect binary tree of height h, the number of nodes is:

Here h is measured in edges and N is the total number of nodes. This formula applies only to perfect binary trees. Consequently, a perfect tree with h = 3 has N = 2⁴ − 1 = 15 nodes. A general binary tree can contain far fewer nodes at the same height.

A binary tree may be represented with linked nodes or, especially when complete, with an array. In a zero-based array, the left child of index i is at 2i + 1 and the right child at 2i + 2, provided those positions exist. The parent of a non-root node at index i is at floor((i − 1) ÷ 2). These relationships are particularly useful for heaps.

A node class

Java:

class Node {
    int value;
    Node left, right;

    Node(int value) {
        this.value = value;
    }
}

Python:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

For production software, a generic node type is preferable: Java can use Node<T>, while Python can use type hints such as Node[T]. If values are mutable or have unusual comparison rules, the ordering policy should be documented explicitly.

2. Traversing Binary Trees

Traversal means visiting every node according to a defined order. The three depth-first traversals are:

• Preorder: root, left subtree, right subtree.
• Inorder: left subtree, root, right subtree.
• Postorder: left subtree, right subtree, root.

Level-order traversal visits nodes one level at a time from left to right and uses a queue.

For the tree below, the traversals are shown as sequences:

8
      /   \
     3     10
    / \      \
   1   6      14
      / \    /
     4   7  13

Inorder traversal becomes especially important for a BST because it produces sorted order.

Recursive traversal

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.value, end=" ")
    inorder(node.right)

The equivalent Java method is:

static void inorder(Node node) {
    if (node == null) return;
    inorder(node.left);
    System.out.print(node.value + " ");
    inorder(node.right);
}

Each node is visited once, so traversal takes O(n) time, where n is the number of nodes. Recursive depth is O(h), where h is tree height. A highly skewed tree can therefore cause stack overflow for very large inputs. Iterative traversal replaces the call stack with an explicit stack.

def iterative_inorder(root):
    stack, current, result = [], root, []
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.value)
        current = current.right
    return result

Level-order traversal uses O(w) auxiliary space, where w is the maximum width of the tree:

from collections import deque

def level_order(root):
    if root is None:
        return []
    queue, result = deque([root]), []
    while queue:
        node = queue.popleft()
        result.append(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

Expression trees

An expression tree represents operators as internal nodes and operands as leaves. For the expression (a + b) × c, the + node has a and b as children, and the × node has the resulting subtree and c as children. Preorder corresponds to prefix notation, inorder to infix notation, and postorder to postfix notation. A postorder evaluator can evaluate an expression by recursively evaluating operands before applying the operator. A robust implementation must validate operators, operand counts, division by zero, and input types.

3. Binary Search Trees

A BST is a binary tree satisfying an ordering invariant. For every node with key k:

• keys in the left subtree are less than k;
• keys in the right subtree are greater than k.

Duplicate keys require a policy: duplicates may be rejected, counted in a frequency field, or placed consistently on one side. A frequency field is often the clearest choice.

Search and insertion

def search(root, key):
    current = root
    while current is not None:
        if key == current.value:
            return current
        current = current.left if key < current.value else current.right
    return None

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.value:
        root.left = insert(root.left, key)
    elif key > root.value:
        root.right = insert(root.right, key)
    return root

The algorithms rely on the invariant. If a node is smaller than the current key, the search need not inspect the right subtree, because every right-subtree key is already known to be larger.

If the tree height is h, search and insertion take O(h) time. In a well-shaped tree, h is approximately log₂ n, giving O(log n) behaviour. In the worst case, inserting sorted data produces a chain with h = n − 1, giving O(n) time. The asymptotic bound is therefore O(log n) average or expected under suitable shape assumptions, but O(n) worst case for an ordinary unbalanced BST.

Deletion

Deletion has three cases:

1. A leaf is removed directly.
2. A node with one child is replaced by that child.
3. A node with two children is replaced by its inorder successor (the minimum key in its right subtree) or inorder predecessor (the maximum key in its left subtree), after which the replacement node is deleted from its original position.

def delete(root, key):
    if root is None:
        return None
    if key < root.value:
        root.left = delete(root.left, key)
    elif key > root.value:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        successor = root.right
        while successor.left:
            successor = successor.left
        root.value = successor.value
        root.right = delete(root.right, successor.value)
    return root

Deletion preserves the ordering invariant if replacement and duplicate policies are applied consistently. In a mutable implementation, references and ownership should be documented; careless sharing of nodes can make one logical tree unexpectedly modify another.

4. Height, Balance, and Balanced Search Trees

A tree is balanced when its height is controlled relative to the number of nodes. Balance does not mean that every node has exactly equal-sized subtrees. It means that the structure prevents long, unnecessary chains.

A height-balanced tree commonly satisfies a bound on the difference between the heights of left and right subtrees. In an AVL tree, for every node:

The expression is a local condition, but it implies logarithmic global height. When insertion or deletion violates the condition, rotations restore it. A right rotation and a left rotation change links while preserving inorder key order. Double rotations handle the left-right and right-left cases.

A red–black tree stores one extra colour bit per node and enforces colour and black-height rules. Its balance is less strict than AVL balance, but updates generally require fewer rotations. Java’s TreeMap and TreeSet are commonly implemented using a red–black tree, providing ordered operations in O(log n) time. The precise library implementation should be checked against the relevant Java documentation rather than assumed in unrelated languages.

Balanced trees are valuable in ordered maps, schedulers, symbol tables, range queries, and database indexes. They are not automatically superior: a hash table usually offers faster expected exact lookup but does not naturally support sorted traversal or range queries.

5. Heaps and Priority Queues

A heap is a complete binary tree with a heap-order property. In a min-heap, each parent key is less than or equal to its children; in a max-heap, each parent key is greater than or equal to its children. A heap does not provide complete sorted order. It guarantees only that the root is the minimum or maximum.

Because a heap is complete, it is efficiently stored in an array. For zero-based index i:

• left child = 2i + 1;
• right child = 2i + 2;
• parent = floor((i − 1) ÷ 2), for i > 0.

The principal operations are:

Insertion appends an item and repeatedly swaps it upward (sift up). Removing the root moves the last item to the root and repeatedly swaps it downward (sift down). Building a heap by bottom-up sift-down is O(n), not O(n log n), because most nodes are near the leaves and move only a short distance.

Python provides heapq, a min-heap module:

import heapq

h = []
heapq.heappush(h, (3, "medium"))
heapq.heappush(h, (1, "urgent"))
priority, task = heapq.heappop(h)  # (1, "urgent")

Tuple ordering makes the priority the first comparison field. If equal-priority records contain incomparable objects, add a unique sequence number as a tie-breaker. Java provides PriorityQueue; its head is the least element according to natural ordering or a supplied comparator. Neither structure should be used when iteration in sorted order is required without repeated removals.

Top-k queries

To find the k largest values in a stream of n values while keeping memory near k, maintain a min-heap of size at most k. For each value x, insert it; if the heap exceeds k, remove the smallest. The final heap contains the k largest values, although not necessarily in sorted order. Time is O(n log k) and auxiliary space is O(k), assuming k ≤ n. For k = 10 and millions of records, this is usually preferable to fully sorting all records, which costs O(n log n).

6. Tries and Prefix Search

A trie (prefix tree) stores strings by sharing nodes for common prefixes. Each edge represents a character; a node records whether a complete word ends there and may store frequency, payload, or ranking information.

Searching for a word of length L takes O(L) time, independent of the number of stored words, assuming character-child access is O(1) or treated as bounded by a fixed alphabet. With a map of children, practical time also depends on map operations. A trie can use more memory than a hash table because it stores many nodes and references.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
        self.frequency = 0

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True
        node.frequency += 1

    def contains(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_word

To implement autocomplete, first follow the prefix to its terminal node, then perform DFS or best-first exploration below that node. A practical service stores the highest-ranked suggestions at each prefix node, reducing response time at the cost of update complexity and memory. Unicode requires a clear policy for case folding, accents, normalization, and grapheme clusters; treating every byte as a character can produce incorrect user-visible results.

Compressed tries, also called radix trees, merge chains of single-child nodes and reduce memory use. Ternary search tries replace a potentially large child map with character comparisons among left, middle, and right links. These are engineering alternatives, not universally superior replacements.

7. Applied Case: An Educational Course Platform

Background. An illustrative online learning platform stores courses in categories, offers autocomplete for course searches, schedules background jobs, and displays popular courses.

Problem. The platform needs four different operations: represent category hierarchy; search courses by title prefix; execute jobs by urgency; and return the ten most-viewed courses from a continuous event stream.

Analysis. A single structure would create unnecessary trade-offs. The category hierarchy is naturally a general tree, while parsed course prerequisites can be represented as a directed graph if cycles and multiple parents are possible. A trie is appropriate for title-prefix lookup. A priority queue is appropriate for jobs because only the next highest-priority job must be selected. A bounded min-heap is appropriate for top-ten processing. An ordered map or balanced tree is useful for range queries such as all courses whose ratings lie between two values.

Approach. Each category node stores child categories and courses. Titles are normalised according to a documented Unicode and case policy before insertion into a trie. Each suggestion stores a course identifier and ranking score; ranking is periodically refreshed rather than trusting unvalidated user input. Jobs are stored in a Java PriorityQueue or Python heapq structure with priority and sequence number. A min-heap of size ten processes view events.

Outcome. Prefix lookup depends primarily on prefix length, job selection is logarithmic in the number of queued jobs, and top-ten maintenance costs O(n log 10), effectively linear in the event count. The design separates semantic requirements instead of forcing hierarchical, ordered, and priority data into one structure.

Learning points. Data-structure selection follows the query pattern. Search indexes need normalization and privacy controls. Priority values require tie-breaking and validation. Cached autocomplete results must have freshness and deletion policies. If course titles or usage data contain personal information, access control, retention, and audit requirements apply.

8. Implementation Practice and Professional Concerns

Invariants and testing

Tree implementations should test invariants after operations. For a BST, an inorder traversal must be sorted according to the chosen duplicate policy. For a heap, every parent must satisfy the heap-order relation. For a trie, every stored word must be discoverable and every unmarked prefix must not be reported as a complete word.

Useful tests include empty structures, one-node structures, duplicate keys, deletion of the root, deletion of nodes with zero, one, and two children, highly sorted insertion sequences, Unicode strings, and very large inputs. Property-based testing can generate random insertion and deletion sequences and compare results with a trusted sorted list or set.

Complexity and memory

Big-O notation describes growth, not exact runtime. A trie with O(L) lookup may still be slower than a hash table for short strings if its nodes cause cache misses. A balanced tree’s O(log n) guarantee may be preferable to a hash table’s expected O(1) when worst-case predictability and range operations matter. Measure representative workloads rather than choosing solely from asymptotic labels.

Concurrency and safety

Most basic tree classes are not thread-safe. Concurrent readers and writers need locks, immutable snapshots, copy-on-write, or specialised concurrent structures. A priority queue used by multiple worker threads needs coordination around both insertion and removal. Recursive algorithms should be reviewed against language recursion limits and adversarially shaped input.

Contemporary developments

Database systems often use B-trees or B+ trees rather than binary trees because high fan-out reduces disk and storage-page accesses. Search engines combine inverted indexes, tries, finite-state structures, and ranking systems. Machine-learning systems use tree ensembles and differentiable tree-like models, but these are conceptually distinct from mutable data-structure trees. Modern autocomplete systems may combine tries with language models; the trie narrows candidates while a model ranks contextually plausible completions. Such systems require careful monitoring for bias, inappropriate suggestions, data leakage, and abuse.

Best-Practice Checklist

1. State the ordering, duplicate, null, and comparison policies.
2. Preserve and test structural invariants after every update.
3. Use iterative traversal when input depth may be adversarial.
4. Choose balanced trees when ordered worst-case performance matters.
5. Use heaps only for priority access, not arbitrary sorted searching.
6. Use tries when prefix operations justify their memory cost.
7. Add stable tie-breakers to priority records.
8. Separate data normalisation, indexing, ranking, and access control.
9. Document complexity, ownership, mutability, and thread-safety assumptions.
10. Benchmark realistic data, including worst-shaped trees and multilingual text.

Chapter Summary

Trees model hierarchical relationships through nodes, edges, roots, leaves, depth, and height. Binary-tree traversals include preorder, inorder, postorder, and level order; they support expression processing, copying, serialisation, and inspection. A BST adds an ordering invariant, making search, insertion, and deletion O(h), where h is the tree height. Without balancing, h can become linear; AVL and red–black trees maintain logarithmic height through structural rules and rotations.

Heaps are complete binary trees designed for priority access. They support constant-time root inspection and logarithmic insertion and root removal, making them suitable for priority queues and top-k streaming queries. Tries organise strings by shared prefixes and provide efficient prefix lookup and autocomplete, although they may consume substantial memory. Professional implementations depend on explicit invariants, duplicate policies, Unicode handling, complexity analysis, testing, and concurrency decisions. The correct structure is determined by the dominant operations: hierarchy, ordered lookup, priority selection, or prefix matching.

Key Terms

Tree: A hierarchical collection of connected nodes.

Node: An element containing data and links to related nodes.

Root: The unique node with no parent.

Leaf: A node with no children.

Height: The maximum number of downward edges from a node to a leaf.

Depth: The number of edges from the root to a node.

Binary tree: A tree in which each node has at most two children.

Traversal: A systematic process for visiting tree nodes.

Binary search tree: A binary tree ordered so left keys are smaller and right keys larger.

Inorder traversal: Left, root, right visitation order.

Rotation: A local restructuring that preserves BST inorder order.

Balanced tree: A tree whose height is controlled relative to its node count.

AVL tree: A height-balanced BST with subtree-height differences at most one.

Red–black tree: A coloured balanced BST with logarithmic-height guarantees.

Heap: A complete binary tree satisfying a parent–child priority relation.

Priority queue: An abstract structure that removes the highest- or lowest-priority item.

Trie: A prefix tree for storing strings by character paths.

Autocomplete: Generation of completions matching a supplied prefix.

Top-k query: A query requesting the k highest- or lowest-ranked items.

Invariant: A condition that must remain true throughout an algorithm or data structure.

Review Questions

5 Short Answer Questions

1. Distinguish the depth and height of a tree node.
2. Why does inorder traversal of a valid BST produce sorted keys?
3. State the three cases that arise when deleting a node from a BST.
4. What property makes an array representation efficient for a heap?
5. Why can a trie support prefix lookup efficiently?

5 Long Answer Questions

1. Explain preorder, inorder, postorder, and level-order traversal, including one practical use for each.
2. Describe BST insertion and deletion and analyse their best, typical, and worst-case time behaviour.
3. Compare AVL trees and red–black trees in terms of balance, updates, and applications.
4. Explain heap insertion, root removal, bottom-up construction, and their complexities.
5. Design a trie-based autocomplete component and discuss ranking, memory, Unicode, and deletion issues.

3 Analytical / Application Questions

1. A system receives millions of scores and must continuously retain the ten largest scores. Choose a structure, provide the algorithm, and justify its time and space complexity.
2. A database needs exact lookup, sorted iteration, and range queries with predictable worst-case performance. Compare a hash table, ordinary BST, and balanced BST, then recommend one.
3. Given a sequence of sorted keys inserted into an ordinary BST, explain the resulting shape and propose two technically different ways to prevent linear-height performance.

Multiple Choice Questions with Answers

Question 1

Which traversal visits a BST's keys in nondecreasing order when the tree is valid and duplicates are handled consistently?

A. Preorder

B. Inorder

C. Postorder

D. Level-order

Correct Answer: B. Inorder

Question 2

What is the worst-case search time in an unbalanced BST containing n nodes?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

Correct Answer: C. O(n)

Question 3

Which operation is guaranteed to be O(1) in a binary min-heap?

A. Finding an arbitrary value

B. Peeking at the minimum root

C. Inserting a value

D. Removing the minimum

Correct Answer: B. Peeking at the minimum root

Question 4

For a zero-based heap array, what is the left-child index of a node at index i?

A. i + 1

B. 2i

C. 2i + 1

D. 2i + 2

Correct Answer: C. 2i + 1

Question 5

Which structure is most directly suited to prefix-based autocomplete?

A. Trie

B. Max-heap

C. Stack

D. Disjoint-set forest

Correct Answer: A. Trie

Question 6

What is the principal purpose of rotations in AVL trees?

A. To sort all keys directly

B. To restore balance while preserving inorder order

C. To convert a tree into a heap

D. To remove all duplicate keys

Correct Answer: B. To restore balance while preserving inorder order

Question 7

A bounded min-heap of size k processes n stream values to retain the k largest values. What is the usual time complexity?

A. O(k)

B. O(log n)

C. O(n log k)

D. O(n²)

Correct Answer: C. O(n log k)

Question 8

Which deletion case in a BST requires finding an inorder successor or predecessor?

A. Deleting a leaf

B. Deleting the root only

C. Deleting a node with two children

D. Deleting an empty tree

Correct Answer: C. Deleting a node with two children

Question 9

What does a heap-order property guarantee in a min-heap?

A. All array values are globally sorted

B. Every parent is less than or equal to its children

C. Every leaf is smaller than the root

D. The tree is always height-balanced as an AVL tree

Correct Answer: B. Every parent is less than or equal to its children

Question 10

Which structure is generally most appropriate for predictable ordered range queries?

A. Balanced search tree

B. Unordered hash table

C. Circular queue

D. Simple stack

Correct Answer: A. Balanced search tree