Trees, Binary Search Trees, and Heaps

Introduction

Many applications must represent relationships that are hierarchical rather than merely sequential. A file system contains folders and files, an organisation contains managers and reporting units, and a compiler represents expressions as nested structures. Linear structures such as arrays, linked lists, stacks, and queues are often insufficient for these relationships. Trees provide a flexible non-linear structure for representing hierarchy, searching, indexing, parsing, and scheduling.

This chapter introduces rooted trees, binary trees, binary search trees, balanced-tree principles, heaps, and priority queues. It also develops the principal traversal and update algorithms and considers their use in Java and Python applications.

Learning Objectives

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

• identify the terminology and structural properties of trees;
• perform preorder, inorder, postorder, and level-order traversals;
• implement and analyse binary search tree operations;
• explain why unbalanced search trees can become inefficient;
• describe the purpose of balanced trees and rotations;
• implement a binary heap and a priority queue;
• select an appropriate tree or heap for a practical application;
• evaluate correctness, efficiency, and limitations of hierarchical data structures.

1. Tree Terminology and Structure

A tree is a connected, acyclic graph consisting of vertices, also called nodes, joined by edges. In programming, trees are normally represented with references from parent nodes to child nodes. One node is designated the root. Every other node has exactly one parent, while a parent may have zero or more children.

Important terms include:

• Root: the unique node with no parent.
• Parent and child: directly connected nodes in which the first is above the second.
• Siblings: nodes with the same parent.
• Leaf: a node with no children.
• Internal node: a node with at least one child.
• Subtree: a node together with all of its descendants.
• Depth: the number of edges from the root to a node. The root has depth 0.
• Height of a node: the greatest number of edges on a downward path from that node to a leaf.
• Height of a tree: the height of its root.
• Degree of a node: its number of children.
• Ancestor and descendant: nodes above and below another node in the hierarchy.

A tree containing n nodes has n - 1 edges. This follows because the root contributes no parent edge and every remaining node has exactly one parent. A tree with one node therefore has height 0 under the edge-count convention. Some texts count levels instead; implementations should state which convention they use.

Figure: A rooted tree illustrating parent–child relationships and depth.

A binary tree is a tree in which each node has at most two children. The children are conventionally named left and right, so their order matters. A binary tree is full if every node has either zero or two children, complete if every level except possibly the last is full and the last is filled from left to right, and perfect if all internal nodes have two children and all leaves occur at the same depth.

These definitions are distinct. A complete tree need not be full, and a full tree need not be complete.

2. Tree Representations

A linked representation stores a node object containing a value and references to children. A binary-tree node can be represented as follows.

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

An equivalent Java class might use fields such as int value, Node left, and Node right. Linked nodes are appropriate when the tree changes frequently or is not complete.

Complete binary trees are efficiently stored in arrays. With zero-based indexing, the node at index i has:

Here i is a valid array index and ⌊x⌋ denotes the floor of x. These relationships assume zero-based indexing and are especially useful for heaps. Array storage wastes space for sparse or highly irregular trees, whereas linked storage requires reference fields but represents sparse structures naturally.

3. Tree Traversals

A traversal visits every reachable node according to a defined order. If a tree contains n nodes, a traversal normally takes O(n) time because each node is processed once. Recursive algorithms use call-stack space proportional to tree height, O(h), where h is the tree height.

Preorder Traversal

Preorder processes the current node, then the left subtree, then the right subtree:

preorder(node):
    if node is not null:
        visit(node)
        preorder(node.left)
        preorder(node.right)

It is useful for copying a tree, producing a prefix expression, or serialising a hierarchy while retaining parent-before-child order.

Inorder Traversal

Inorder processes the left subtree, current node, and right subtree:

inorder(node):
    if node is not null:
        inorder(node.left)
        visit(node)
        inorder(node.right)

For a binary search tree, inorder traversal produces keys in nondecreasing order. This property makes it useful for sorted output and validation.

Postorder Traversal

Postorder processes the left subtree, right subtree, and current node:

postorder(node):
    if node is not null:
        postorder(node.left)
        postorder(node.right)
        visit(node)

A node is processed after its descendants. Consequently, postorder is appropriate for deleting a tree, evaluating expression trees, and calculating directory sizes.

Level-Order Traversal

Level-order traversal visits nodes breadth-first, from the root downward. It uses a queue:

level_order(root):
    if root is null: return
    queue.enqueue(root)
    while queue is not empty:
        node = queue.dequeue()
        visit(node)
        if node.left is not null: queue.enqueue(node.left)
        if node.right is not null: queue.enqueue(node.right)

Its time complexity is O(n), and its auxiliary space is O(w), where w is the maximum width of the tree. Level-order traversal is useful for printing organisational levels and inspecting complete trees.

For example, if a binary tree has root 8, children 3 and 10, and 3 has children 1 and 6, then preorder begins 8, 3, 1, 6, 10; inorder is 1, 3, 6, 8, 10; postorder is 1, 6, 3, 10, 8; and level-order is 8, 3, 10, 1, 6.

4. Binary Search Trees

A binary search tree (BST) is a binary tree obeying an ordering rule. For each node with key k, every key in its left subtree is less than k, and every key in its right subtree is greater than k, assuming duplicate keys are disallowed. If duplicates are allowed, the implementation must specify whether equal keys go consistently left, consistently right, or are stored with a count.

Searching

To search for key x, compare it with the current node. If equal, the search succeeds. If x is smaller, continue left; otherwise continue right.

def search(node, x):
    while node is not None:
        if x == node.value:
            return node
        node = node.left if x < node.value else node.right
    return None

The running time is O(h). In a well-shaped tree, h is approximately logarithmic in n; in the worst case, inserting already sorted values can create a chain with h = n − 1, making search O(n).

Insertion

Insertion follows the same comparisons until it reaches an empty child position. The new key is placed there. Inserting 50, 30, 70, 20, and 40 produces a root 50, with 30 and 70 below it, and 20 and 40 below 30.

def insert(node, x):
    if node is None:
        return Node(x)
    if x < node.value:
        node.left = insert(node.left, x)
    elif x > node.value:
        node.right = insert(node.right, x)
    return node                 # duplicate policy: ignore duplicates

The recursive function returns the possibly updated subtree root. This detail is essential when inserting into an empty tree or replacing a child reference.

Deletion

Deletion has three cases:

1. Leaf: remove the node by setting its parent’s reference to null.
2. One child: replace the node with its only child.
3. Two children: replace the node’s key with its inorder successor—the smallest key in the right subtree—or its inorder predecessor, then delete that replacement node.

The two-child case preserves the ordering invariant. Its time complexity is O(h), although finding and removing the successor must both be included in the analysis.

Correctness Invariant

The central BST invariant is that every node divides the key space into a left interval and a right interval. Search, insertion, and deletion are correct only if every update preserves this invariant. A practical validation routine should carry allowable lower and upper bounds while recursively inspecting nodes, rather than merely checking each node against its immediate children.

5. Balanced Trees and Rotations

A BST is efficient when its height is small. However, ordinary insertion does not guarantee a small height. Inserting 10, 20, 30, 40, and 50 into an initially empty BST produces a right-skewed chain. Although the structure is technically a BST, it behaves like a linked list.

A balanced tree limits height in relation to the number of nodes. For logarithmic performance, the desired relationship is approximately h = O(log n). The base of a logarithm affects the numerical value but not the asymptotic classification when the base is a fixed constant greater than 1.

A rotation changes local links while preserving inorder key order. A left rotation around node x promotes its right child and moves that child’s left subtree to become x’s right subtree. A right rotation is the mirror image. Rotations take O(1) time because they modify a fixed number of references.

Two common balanced-tree families are:

• AVL trees: maintain a balance factor, usually defined as left-subtree height minus right-subtree height, constrained to −1, 0, or +1 at every node. Violations are corrected with single or double rotations.
• Red–black trees: assign a colour to each node and maintain colouring rules that guarantee height O(log n). They usually perform fewer structural adjustments than AVL trees during updates and are widely used in standard libraries.

At certificate level, the important design principle is not memorising every balancing case but recognising that balanced trees exchange additional update bookkeeping for predictable search performance. Python’s built-in dictionary is hash-based rather than a user-visible balanced BST; Java’s TreeMap is commonly implemented using a red–black tree and provides ordered map operations.

6. Heaps

A heap is a specialised complete binary tree satisfying a local ordering condition. In a min-heap, every parent key is less than or equal to its children; therefore the minimum key is at the root. In a max-heap, every parent key is greater than or equal to its children, so the maximum is at the root.

The heap property is not the same as complete global sorting. For example, nodes in separate subtrees need not be ordered relative to each other. Consequently, a heap is excellent for repeatedly obtaining the extreme priority but is not efficient for arbitrary sorted traversal.

Because a heap is complete, an array is the natural representation. The fundamental operations are:

• peek: return the root in O(1) time;
• insert: append the new item and repeatedly swap it with its parent while it violates the heap property; this is called sift-up or bubble-up and takes O(log n) time;
• remove-min/remove-max: move the last item to the root, reduce the size, and repeatedly swap it with the more appropriate child; this is sift-down and takes O(log n) time;
• build-heap: transform an arbitrary array into a heap by sift-down processing from the last internal node toward the root. This takes O(n) time, not O(n log n) when implemented with bottom-up construction.

The O(n) build-heap result follows because many nodes are near the leaves and require little movement; the sum of their possible movement costs is linear. Repeatedly inserting n items into an initially empty heap gives O(n log n).

A compact min-heap insertion is:

def push(heap, item):
    heap.append(item)
    i = len(heap) - 1
    while i > 0:
        p = (i - 1) // 2
        if heap[p] <= heap[i]:
            break
        heap[p], heap[i] = heap[i], heap[p]
        i = p

In real applications, a priority item may be a tuple such as (priority, sequence_number, task). The sequence number supplies deterministic tie-breaking when tasks have equal priority.

7. Priority Queues

A priority queue removes the item with the highest priority rather than necessarily the item that arrived first. A min-priority queue removes the smallest priority value; a max-priority queue removes the largest. A heap is a common implementation, but a priority queue is an abstract data type and could also be implemented using an unsorted array, sorted array, or balanced tree.

A priority queue is appropriate when the dominant workflow is “add work, then repeatedly process the most urgent work.” It is not automatically appropriate when arbitrary search, range queries, or complete sorted access is required.

8. Applied Case: Emergency Service Dispatch

Background

Consider an illustrative emergency-service dispatch system receiving incidents from multiple locations. Each incident has a severity level, arrival time, location, and identifying number. Dispatchers must select the next incident while avoiding indefinite postponement of older incidents.

Problem

A simple FIFO queue treats all incidents equally, while repeatedly scanning an unsorted list takes O(n) time for each dispatch. The system needs rapid access to the most urgent incident and a transparent tie-breaking rule.

Analysis and Solution

The system uses a min-heap whose comparison key is (severity_rank, arrival_sequence), where a smaller severity rank means greater urgency. For equal severity, the smaller arrival sequence is selected first. Insertion and removal each take O(log n), while viewing the next incident takes O(1).

The application should maintain an immutable incident identifier and record every enqueue, priority change, dispatch, cancellation, and operator override. If priorities can change, one safe design is to insert a new record with the updated priority and mark the old record as cancelled; stale records are discarded when they reach the root. Another design supports an indexed heap with direct position tracking, but it is more complex.

Outcome

The heap improves dispatch scalability and makes the selection policy explicit. However, a purely severity-based policy can starve lower-priority incidents. A governance rule may therefore increase the effective priority of waiting incidents after a defined period, subject to operational approval.

Learning Points

The data structure does not determine policy by itself. The heap efficiently enforces the comparison rule supplied by the application. Correctness also requires clear definitions of priority, tie-breaking, cancellation, auditing, and exceptional human intervention.

9. Application Design and Implementation Guidance

When choosing among structures, begin with operations rather than with a preferred data structure. Use a general tree when relationships are hierarchical but not ordered. Use a BST or ordered map when sorted search, predecessor/successor queries, and range operations matter. Use a heap when only the current minimum or maximum is repeatedly required. Use a trie for prefix-oriented string lookup, although tries have different memory characteristics and are beyond the main scope of this chapter.

Good implementations should:

• define whether duplicate keys are permitted;
• document whether height counts edges or nodes;
• handle empty trees and missing keys explicitly;
• preserve parent-child references during updates;
• test all deletion cases in a BST;
• test heap operations after each mutation;
• avoid recursion for extremely deep unbalanced trees unless stack limits are understood;
• use stable tie-breaking when equal priorities require predictable behaviour;
• separate the abstract data type from user-interface and persistence code.

Testing should include an empty structure, one node, repeated values, already sorted input, reverse-sorted input, random input, deletion of the root, deletion of leaves, and large workloads. For a BST, an inorder traversal can be checked for sortedness, but sortedness alone does not prove that every structural invariant is valid.

10. Limitations, Security, and Contemporary Practice

Trees consume memory for references, object headers, and auxiliary metadata. Pointer-heavy structures may also have poor cache locality compared with arrays. Recursion is elegant but can fail on a highly skewed tree. Balanced structures reduce worst-case height but increase implementation complexity.

Untrusted input deserves special attention. If a service accepts keys in an order that causes ordinary BST degeneration, an attacker may induce excessive running time. Balanced trees, randomized priorities, input limits, or library implementations can reduce this risk. Heap-based scheduling systems must protect priority fields from unauthorised manipulation because changing a priority can change the order of service.

Libraries are usually preferable to handwritten balanced trees in production. Java provides PriorityQueue and ordered collections such as TreeMap; Python provides heapq, which implements a min-heap over a list. Library documentation must be checked for details such as whether operations are stable, whether removal of arbitrary elements is efficient, and whether thread safety is provided. AI-assisted code generation may help produce test cases or boilerplate, but generated algorithms must be reviewed for duplicate handling, null behaviour, index errors, and invariant preservation.

Chapter Summary

Trees represent hierarchical relationships using nodes, edges, roots, parents, children, leaves, depth, and height. Binary trees restrict each node to at most two children. Preorder, inorder, postorder, and level-order traversals provide different processing sequences and all visit every node in linear time.

A binary search tree maintains an ordering invariant that supports search, insertion, and deletion in O(h), where h is height. Balanced-tree methods, including AVL and red–black techniques, maintain logarithmic height and avoid the linear-time worst case of a skewed BST. Rotations preserve inorder ordering while changing local structure.

A heap is a complete binary tree with a parent-child priority property. Array indexing makes heaps compact, and binary-heap insertion and removal take O(log n), while peeking takes O(1). Priority queues use these operations to schedule work. Effective professional solutions combine a suitable data structure with explicit duplicate, tie-breaking, cancellation, testing, security, and governance policies.

Key Terms

Tree: A connected acyclic structure of nodes and edges.

Root: The node with no parent.

Leaf: A node with no children.

Subtree: A node and all of its descendants.

Depth: Number of edges from the root to a node.

Height: Greatest downward path length from a node to a leaf.

Binary tree: A tree with at most two children per node.

Full binary tree: A binary tree in which each node has zero or two children.

Complete binary tree: A tree filled by levels, with the final level filled left to right.

Traversal: A systematic process for visiting tree nodes.

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

BST invariant: The ordering condition that must hold throughout a binary search tree.

Rotation: A local restructuring that preserves inorder key order.

Balanced tree: A tree whose height is controlled relative to its number of nodes.

Heap: A complete tree satisfying a parent-child priority property.

Min-heap: A heap whose smallest key is at the root.

Priority queue: An abstract data type that removes items by priority.

Sift-up: Moving a newly inserted heap item toward the root.

Sift-down: Moving a replacement root toward an appropriate leaf position.

Starvation: Indefinite postponement of a low-priority item.

Review Questions

Short Answer Questions

1. Define the height of a tree under the edge-count convention.
2. What order does inorder traversal produce for a valid BST?
3. State the three structural cases in BST deletion.
4. Why is a binary heap naturally stored in an array?
5. What is the difference between a min-heap and a max-heap?

Long Answer Questions

1. Explain preorder, inorder, postorder, and level-order traversal, including one suitable application for each.
2. Describe BST search and insertion and explain how an unbalanced tree affects their complexity.
3. Explain how rotations support balanced-tree implementations.
4. Compare a BST, a balanced tree, and a heap in terms of ordering, operations, and applications.
5. Explain bottom-up heap construction and why its complexity is O(n) rather than O(n log n).

Analytical / Application Questions

1. Insert 40, 20, 60, 10, 30, 50, and 70 into a BST. Give its inorder and level-order traversals, then delete 40 using its inorder successor.
2. Design a priority queue for a help-desk system in which urgent tickets are processed first but equal-priority tickets retain arrival order. Specify the heap key and explain how cancellation would be handled.
3. A program receives keys in sorted order and uses an ordinary BST. Analyse the resulting performance and recommend two design alternatives, explaining their trade-offs.

Multiple Choice Questions with Answers

Question 1

Which traversal visits a BST’s keys in nondecreasing order?

A. Preorder

B. Inorder

C. Postorder

D. Level-order

Correct Answer: B. Inorder

Question 2

What is the worst-case time complexity of searching an ordinary BST with height h?

A. O(1)

B. O(log h)

C. O(h)

D. O(h²)

Correct Answer: C. O(h)

Question 3

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

A. Deleting a leaf

B. Deleting the root only

C. Deleting a node with one child

D. Deleting a node with two children

Correct Answer: D. Deleting a node with two children

Question 4

In a zero-based array representation of a binary heap, what is the left child index of node i?

A. 2i

B. 2i + 1

C. 2i + 2

D. i ÷ 2

Correct Answer: B. 2i + 1

Question 5

Which operation on a binary heap normally takes O(1) time?

A. Peek at the root

B. Insert an item

C. Remove the root

D. Find an arbitrary item

Correct Answer: A. Peek at the root

Question 6

What property distinguishes a complete binary tree?

A. Every node has exactly two children

B. All keys are globally sorted

C. Levels are filled except possibly the last, which is filled left to right

D. Every leaf has the same key

Correct Answer: C. Levels are filled except possibly the last, which is filled left to right

Question 7

What is the principal purpose of rotations in balanced BSTs?

A. To remove all duplicate keys

B. To preserve ordering while controlling height

C. To convert a tree into a linked list

D. To sort an unrelated array

Correct Answer: B. To preserve ordering while controlling height

Question 8

Which structure is most suitable for repeatedly processing the smallest priority value?

A. Min-heap priority queue

B. Stack

C. Unsorted graph

D. Circular buffer only

Correct Answer: A. Min-heap priority queue

Question 9

What is the time complexity of bottom-up construction of a binary heap from n items?

A. O(1)

B. O(log n)

C. O(n)

D. O(n²)

Correct Answer: C. O(n)

Question 10

In a priority queue, what problem can occur if high-priority items continually arrive?

A. Underflow of every tree

B. Starvation of lower-priority items

C. Automatic sorting of all input

D. Loss of the root’s parent

Correct Answer: B. Starvation of lower-priority items