Tree properties, spanning trees, and traversal algorithms
A tree is a connected graph with no cycles -- there is exactly one path between any two vertices. Trees appear everywhere in computer science: file systems, HTML documents, decision trees, and search indices.
In this section you will learn to identify trees, find spanning trees using Prim's algorithm, visualize BFS and DFS traversals, and explore the special case of binary trees.
A tree with n vertices always has exactly n - 1 edges. Click vertices to add or remove edges and watch the three tree conditions update in real-time.
Click two vertices to toggle an edge
Key insight: Any two of the three properties -- connected, acyclic, |E| = |V| - 1 -- imply the third. Adding any edge to a tree creates exactly one cycle; removing any edge disconnects it.
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.
Key insight: Prim's greedy strategy -- always pick the minimum-weight crossing edge -- is guaranteed to produce an optimal spanning tree. This is a cornerstone algorithm in network design.
BFS (Breadth-First Search) visits nodes level by level using a queue, while DFS (Depth-First Search) goes deep before backtracking using a stack. Select a traversal type and run the animation.
Key insight: BFS finds shortest paths in unweighted graphs, while DFS is better for exploring all paths or detecting cycles. Both visit every node exactly once in O(V + E) time.
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
Key insight: A full binary tree has every node with 0 or 2 children. The height determines the worst-case search time, making balanced binary trees fundamental to efficient data structures like BSTs and heaps.