Tree properties, spanning trees, and traversal algorithms
A tree connects every vertex with no cycles and not one spare edge. Build one, grow the cheapest one, and watch searches sweep through it.
Click two vertices to toggle an edge and watch the three tree conditions update. Make all three true at once, then add one more edge and see what breaks.
Click two vertices to toggle an edge
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.
A tree with n vertices always has exactly n - 1 edges. 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.
Press Run Prim's Algorithm and watch the tree grow one edge at a time, always taking the cheapest edge that reaches a new vertex.
A spanning tree connects all vertices with exactly |V| - 1 edges. 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.
Pick BFS or DFS and run the animation. Watch the queue or stack fill and empty, and compare the two visit orders.
BFS (Breadth-First Search) visits nodes level by level using a queue, while DFS (Depth-First Search) goes deep before backtracking using a stack. 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.
Click a node to select it, then use Add Left, Add Right, or Remove. Watch the height change and whether the tree stays full.
Click a node to select it
A binary tree is a tree where each node has at most two children: a left child and a right child. 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.
Spot a mistake or have an idea?