Tree and Heap Concepts

Arrays and linked lists put data in a single line. Hierarchical data, such as folders inside folders, an org chart or the tags of an HTML page, does not fit a line well. The structure built for it is the tree. Restrict a tree one way and you get the binary search tree, which finds keys in sorted data quickly. Restrict it another way and you get the heap, which hands you the smallest (or largest) value quickly. This chapter sets up the vocabulary and intuition for all three.

What a tree is

A tree is made of nodes joined by edges, with these properties:

• There is exactly one root at the top.
• Every node except the root has exactly one parent.
• There are no cycles, so there is exactly one path from the root to any node.
• A tree with n nodes always has n - 1 edges.

In graph terms, a rooted tree is a connected acyclic graph with one node chosen as the root.

Vocabulary

The height of a tree is the height of its root. A single-node tree has height 0, and the empty tree is conventionally -1. Some textbooks count height in nodes instead of edges, so check the definition before solving a problem.

Binary trees

A binary tree is a tree where every node has at most two children, called left and right. Common shapes:

• Full: every node has 0 or 2 children.
• Perfect: all leaves are at the same depth and every internal node has two children. A perfect tree of height h has 2^(h+1) - 1 nodes.
• Complete: every level is full except possibly the last, which is filled from the left. Heaps have exactly this shape.
• Degenerate: every node has a single child, so the tree is really a linked list.

In Python a node is a small class.

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


def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))


def size(node):
    if node is None:
        return 0
    return 1 + size(node.left) + size(node.right)


#       8
#      / \
#     3   10
#    / \    \
#   1   6    14
root = Node(8, Node(3, Node(1), Node(6)), Node(10, None, Node(14)))
print(height(root), size(root))  # 2 6

Binary search trees (BST)

A binary search tree is a binary tree where, at every node, all keys in the left subtree are smaller and all keys in the right subtree are larger. Starting at the root, each comparison discards an entire subtree, which is the same effect as binary search on a sorted array. An in-order traversal (left, node, right) visits the keys in ascending order.

The rule applies to whole subtrees, not just to the immediate children. To check that a tree is a BST, pass the allowed range down as you recurse.

def is_bst(node, low=float("-inf"), high=float("inf")):
    if node is None:
        return True
    if not (low < node.key < high):
        return False
    return is_bst(node.left, low, node.key) and is_bst(node.right, node.key, high)


print(is_bst(root))  # True

Why balance matters

Search, insert and delete in a BST cost time proportional to the height h. With well-spread keys, h is about log2 n, but inserting keys in sorted order (1, 2, 3, ...) produces a degenerate tree with h = n - 1. Self-balancing trees fix this by restoring their shape with rotations on every insert and delete. The two best known are the AVL tree, which keeps the height difference between the left and right subtrees of every node at most 1, and the red-black tree, which colours nodes red or black so that no path is more than twice as long as any other. This guide explains the idea only; in practice you use the implementation your language provides.

Heaps and priority queues

A binary heap is a binary tree with two properties. First, its shape is a complete binary tree. Second, in a min-heap every parent is less than or equal to its children (a max-heap is the reverse). The root therefore always holds the minimum, but siblings and separate subtrees are in no particular order. A heap is not sorted like a BST; it only guarantees where the smallest element is.

Because a complete binary tree has no gaps, it can be stored in a plain array in level order, with no pointers.

def parent(i):
    return (i - 1) // 2


def left(i):
    return 2 * i + 1


def right(i):
    return 2 * i + 2


heap = [1, 3, 2, 7, 4, 5]  # a min-heap
for i in range(1, len(heap)):
    assert heap[parent(i)] <= heap[i]
print(heap[0], left(1), right(1))  # 1 3 4

The heap is the most common way to implement a priority queue, an abstract data type that supports "insert a value" and "remove the highest-priority value". With a heap, both operations take O(log n).

Which one to use

• Hierarchical data: a general tree (file systems, the DOM, syntax trees).
• Lookups that also need sorted order, range queries or previous/next values: a balanced BST.
• Repeatedly taking the smallest (or largest) item: a heap or priority queue.
• Lookups by key only: a hash table is usually faster.

Summary

A tree is a hierarchy in which every node is reached from the root by exactly one path. A binary search tree keeps smaller keys on the left and larger keys on the right, and its performance depends on keeping the height low. A heap only maintains a complete shape and parent-child order, which lets it live in an array and implement a priority queue efficiently.