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.
16 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a tree, formally, in discrete math?
- A connected acyclic graph with n vertices and exactly n minus 1 edges
- What is a rooted tree?
- A tree with one designated vertex, called the root, from which all other vertices descend
- What is a leaf, in a tree?
- A vertex with no children
- What is the height of a tree?
- The length of the longest path from the root to any leaf
- What is a binary tree?
- A tree where each vertex has at most two children
- What is a spanning tree?
- A subgraph that includes all vertices of a graph and is itself a tree
- What is a minimum spanning tree?
- A spanning tree with the smallest possible total edge weight
- What algorithm is commonly used to find a minimum spanning tree?
- Kruskal's algorithm or Prim's algorithm
- What is the relationship between vertices and edges in any tree?
- A tree with n vertices always has exactly n minus 1 edges
- What is a forest, in graph theory?
- A collection of disjoint trees
- What is tree traversal?
- The process of visiting every vertex of a tree in a systematic order
- What is preorder traversal?
- Visiting the root, then the left subtree, then the right subtree
- What is inorder traversal?
- Visiting the left subtree, then the root, then the right subtree
- What is postorder traversal?
- Visiting the left subtree, then the right subtree, then the root
- What is a binary search tree?
- A binary tree where left children are smaller and right children are larger than their parent
FlashKeepers