Discrete Math for Computer Science, unit: Trees (Discrete Math). Core concepts, terminology, and worked-example cues a college student meets for this unit, building on prior units without repeating them. Front: a term, concept, or short problem cue. Back: the definition, explanation, or answer.
About this set
38 basic cards for College Computer Science. Set 6 of 8 in Discrete Math for Computer Science. It opens with "What is a tree, formally, in discrete math?" and "What is a rooted tree?". Study it alongside the other College sets below.
38 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a tree, formally, in discrete math?
Show answer
A connected acyclic graph with n vertices and exactly n minus 1 edges- What is a rooted tree?
Show answer
A tree with one designated vertex, called the root, from which all other vertices descend- What is a leaf, in a tree?
Show answer
A vertex with no children- What is the height of a tree?
Show answer
The length of the longest path from the root to any leaf- What is a binary tree?
Show answer
A tree where each vertex has at most two children- What is a spanning tree?
Show answer
A subgraph that includes all vertices of a graph and is itself a tree- What is a minimum spanning tree?
Show answer
A spanning tree with the smallest possible total edge weight- What algorithm is commonly used to find a minimum spanning tree?
Show answer
Kruskal's algorithm or Prim's algorithm- What is the relationship between vertices and edges in any tree?
Show answer
A tree with n vertices always has exactly n minus 1 edges- What is a forest, in graph theory?
Show answer
A collection of disjoint trees- What is tree traversal?
Show answer
The process of visiting every vertex of a tree in a systematic order- What is preorder traversal?
Show answer
Visiting the root, then the left subtree, then the right subtree- What is inorder traversal?
Show answer
Visiting the left subtree, then the root, then the right subtree- What is postorder traversal?
Show answer
Visiting the left subtree, then the right subtree, then the root- What is a binary search tree?
Show answer
A binary tree where left children are smaller and right children are larger than their parent
FlashKeepers