Tree properties, spanning trees, and traversal algorithms
A tree is one of the most important structures in computer science. It's a connected graph with no cycles — meaning there's exactly one path between any two vertices. Trees appear everywhere: file systems, HTML documents, decision trees, and more!
In this section, you'll learn to identify trees, find spanning trees in graphs, traverse trees efficiently, and explore the special case of binary trees.
A tree is a connected graph with no cycles. It always has exactly |V| - 1 edges. Click vertices to add or remove edges and see when the graph becomes a valid tree!
Click two vertices to toggle an edge
A spanning tree connects all vertices with exactly |V| - 1 edges. Watch Prim's algorithm build a minimum spanning tree by always choosing the smallest edge that connects a new vertex!
Watch how BFS (Breadth-First Search) visits nodes level by level, while DFS (Depth-First Search) goes deep before backtracking.
A binary tree is a tree where each node has at most two children: a left child and a right child. Click a node to select it, then add or remove children.
Click a node to select it
1. Tree Properties: A tree is a connected, acyclic graph. With n vertices, it has exactly n-1 edges. There's a unique path between any two vertices. A forest is a graph with no cycles (a collection of trees).
2. Spanning Trees: A spanning tree of a graph connects all vertices with minimum edges. Prim's algorithm builds an MST by greedily adding the minimum weight edge that connects a new vertex.
3. Tree Traversals: BFS uses a queue and visits nodes level by level. DFS uses a stack (or recursion) and explores deep before backtracking. Both visit every node exactly once.
4. Binary Trees: Each node has at most 2 children. Height is the longest root-to-leaf path. A full binary tree has every node with 0 or 2 children. Binary trees are fundamental to search algorithms and data structures.
Next Up: In the next section, you'll learn about paths and cycles — including the famous Königsberg bridge problem, Eulerian paths, and Dijkstra's shortest path algorithm!