Trees and Hash Tables

Binary trees

class TreeNode:n    def __init__(self, value):n        self.value = valuen        self.left = Nonen        self.right = Nonennroot = TreeNode(50)nroot.left = TreeNode(30)nroot.right = TreeNode(70)

A tree organizes data hierarchically — each node can have child nodes, and a binary tree specifically allows at most two children per node. File systems, HTML’s own DOM (covered in the JavaScript course), and this very site’s course → lesson relationship are all naturally tree-shaped.

Binary search trees

def insert(node, value):n    if node is None:n        return TreeNode(value)n    if value < node.value:n        node.left = insert(node.left, value)n    else:n        node.right = insert(node.right, value)n    return node

A binary search tree keeps every left child smaller than its parent and every right child larger — this ordering is what makes searching an O(log n) operation instead of O(n), since each comparison eliminates roughly half the remaining tree, the same idea behind binary search covered in the next lesson.

Hash tables

scores = {}                 # a hash table -- Python's dict, Java's HashMap, Go's mapnscores["Yash"] = 95nscores["Ana"] = 88nprint(scores["Yash"])        # O(1) -- near-instant lookup regardless of size

A hash table converts a key into a number (via a “hash function”) that determines roughly where in memory to store the associated value — this is what gives dictionaries, maps, and hash sets across every language on this site their near-instant O(1) average lookup time, dramatically faster than scanning through a list to find a match.

Hash collisions, briefly

Two different keys can occasionally hash to the same location — called a collision. Every real hash table implementation has a strategy for handling this internally; as a user of a dictionary or map, you never need to think about it directly, but it is worth knowing it is happening under the hood.