---
tag: 0C9J6W2A8A
kind: definition
name: Rooted tree
msc: [05C05]
defines: 0Y0JGC2K9T
uses: [0MJ0JS72DZ]
sources:
  - url: https://en.wikipedia.org/wiki/Tree_(graph_theory)
    locator: Rooted tree
---

## Definition

A rooted tree is a pair $(T, r)$ of a [[tree|0MJ0JS72DZ]] $T$ and a vertex $r$ of $T$, the root.

Let $v \neq r$ be a vertex, and let $u$ be the neighbour of $v$ on the unique path from $v$ to $r$.
Then $u$ is the parent of $v$, and $v$ is a child of $u$.
The depth of $v$ is the [[distance|0WPZ5YPAGR]] from $r$ to $v$.

## Remarks

The root has no parent, and every other vertex has exactly one parent.
A vertex with no child is a leaf of the rooted tree. With this convention the root can be a leaf only when the tree has one vertex.
An ordered rooted tree also fixes an order of the children of each vertex. A [[binary tree|02A8EMC83C]] is a related recursive structure.

## Explanations

### L1 human

A rooted tree is a tree in which one vertex is chosen as the top.
Then each edge has a direction: from a parent toward its child, away from the root.