Computer Science Roadmap

Explanation

A tree is a hierarchical structure made of nodes connected by parent-child links. It has a single root at the top, and every other node has exactly one parent, which means a tree never contains a cycle. A binary tree is the most common kind: each node has at most two children, usually called left and right. A Binary Search Tree (BST) adds a rule — for every node, values in its left subtree are smaller and values in its right subtree are larger — which makes lookups fast. Traversing a tree means visiting its nodes in a systematic order. In-order traversal visits the left subtree, then the node itself, then the right subtree; when applied to a BST it visits the values in sorted order. Pre-order visits the node first, and post-order visits the node last. Which one you pick depends on what you need to compute. A graph is a more general structure: a set of nodes (vertices) connected by edges. Unlike a tree, a graph can have cycles and multiple paths between nodes. Graphs are the model for social networks, maps, and dependencies. They are often stored as an adjacency list — a mapping from each node to the nodes it connects to. A heap is a special tree that keeps the smallest (or largest) value at the root, which is why it powers priority queues. Python provides heaps in the heapq module.

Tree Terminology

Binary Search Trees

1       82      / \3     3   104    / \5   1   66 7To find 6: 8 -> left (6 < 8) -> right (6 > 3). Two comparisons instead of four.

Tree Traversals

Trees vs Graphs

Syntax

1class Node:2    def __init__(self, value):3        self.value = value4        self.left = None5        self.right = None6 7def in_order(node):8    if node is None:9        return10    in_order(node.left)11    print(node.value)12    in_order(node.right)13 14# Graph as an adjacency list15graph = {16    "A": ["B", "C"],17    "B": ["D"],18    "C": [],19    "D": []20}

Recursion mirrors the structure of a tree: each call handles one node and delegates the left and right subtrees to new calls.

Examples

1class Node:2    def __init__(self, value):3        self.value = value4        self.left = None5        self.right = None6 7def insert(root, value):8    if root is None:9        return Node(value)10    if value < root.value:11        root.left = insert(root.left, value)12    else:13        root.right = insert(root.right, value)14    return root15 16def in_order(node):17    if node:18        in_order(node.left)19        print(node.value)20        in_order(node.right)21 22root = None23for v in [5, 2, 8, 1]:24    root = insert(root, v)25 26in_order(root)

1
2
5
8

1graph = {2    "A": ["B", "C"],3    "B": ["D"],4    "C": ["D"],5    "D": []6}7 8for node, neighbors in graph.items():9    print(node, "->", neighbors)

A -> ['B', 'C']
B -> ['D']
C -> ['D']
D -> []

1import heapq2 3heap = []4heapq.heappush(heap, 5)5heapq.heappush(heap, 1)6heapq.heappush(heap, 3)7 8print(heapq.heappop(heap))9print(heapq.heappop(heap))10print(heapq.heappop(heap))

1
3
5