Graphs / Rooted Trees
Least You Need to Know: Rooted Trees
A rooted tree picks one vertex as the root, which gives every other vertex a parent-child relationship and a level.
جو کم از کم جاننا ضروری ہے
- The root has no parent.
- Every non-root vertex has exactly one parent.
- Leaves are vertices with no children.
- Subtrees inherit the tree structure below a chosen vertex.
اہم علامتیں
root
distinguished top vertex
parent(v)
the vertex directly above v
depth
distance from the root
مختصر حل شدہ مثال
- In a rooted tree with root r and edges `r-a, r-b, a-c`, the parent of c is a.
- The leaves are b and c.
- The depth of c is 2 because it is two edges from r.
عام غلطیاں
- Students often think the root is the only vertex allowed to have children.
- Students often call any degree-1 vertex a leaf even when it is the root in a one-vertex tree.
- Students often confuse parent with ancestor.
اس قسم کے سوال کو کیسے پہچانیں
- Every child is one edge farther from the root than its parent.
- Leaves are about children, not total degree in the underlying unrooted tree.
- A subtree includes a vertex and all of its descendants.
Next recommended lesson
Continue through this topic with Least You Need to Know: Trees.
Least You Need to Know: TreesRelated lessons
Keep going with nearby lessons in the same topic.