Editing Tree (graph theory) (section)

===Rooted tree===
A {{em|rooted tree}} is a tree in which one vertex has been designated the root.{{sfn|Bender|Williamson|2010|p=173}} The edges of a rooted tree can be assigned a natural orientation, either away from or towards the root, in which case the structure becomes a directed rooted tree. When a directed rooted tree has an orientation away from the root, it is called an ''arborescence''{{sfn|Deo|1974|p=206}} or ''out-tree'';{{sfn|Deo|1974|p=207}} when it has an orientation towards the root, it is called an ''anti-arborescence'' or ''in-tree''.{{sfn|Deo|1974|p=207}} The tree-order is the [[partial ordering]] on the vertices of a tree with {{math|''u'' < ''v''}} if and only if the unique path from the root to {{mvar|v}} passes through {{mvar|u}}. A rooted tree {{mvar|T}} that is a [[Glossary of graph theory#Subgraphs|subgraph]] of some graph {{mvar|G}} is a [[normal tree]] if the ends of every {{mvar|T}}-path in {{mvar|G}} are comparable in this tree-order {{harv|Diestel|2005|p=15}}. Rooted trees, often with an additional structure such as an ordering of the neighbors at each vertex, are a key data structure in computer science; see [[tree data structure]].

In a context where trees typically have a root, a tree without any designated root is called a ''free tree''.

A ''labeled tree'' is a tree in which each vertex is given a unique label. The vertices of a labeled tree on {{mvar|n}} vertices (for nonnegative integers {{mvar|n}}) are typically given the labels {{math|1, 2, …, ''n''}}. A ''[[recursive tree]]'' is a labeled rooted tree where the vertex labels respect the tree order (i.e., if {{math|''u'' < ''v''}} for two vertices {{mvar|u}} and {{mvar|v}}, then the label of {{mvar|u}} is smaller than the label of {{mvar|v}}).

In a rooted tree, the ''parent'' of a vertex {{mvar|v}} is the vertex connected to {{mvar|v}} on the [[Path (graph theory)|path]] to the root; every vertex has a unique parent, except the root has no parent.{{sfn|Bender|Williamson|2010|p=173}} A ''child'' of a vertex {{mvar|v}} is a vertex of which {{mvar|v}} is the parent.{{sfn|Bender|Williamson|2010|p=173}} An ''ascendant'' of a vertex {{mvar|v}} is any vertex that is either the parent of {{mvar|v}} or is (recursively) an ascendant of a parent of {{mvar|v}}. A ''descendant'' of a vertex {{mvar|v}} is any vertex that is either a child of {{mvar|v}} or is (recursively) a descendant of a child of {{mvar|v}}. A ''sibling'' to a vertex {{mvar|v}} is any other vertex on the tree that shares a parent with {{mvar|v}}.{{sfn|Bender|Williamson|2010|p=173}} A ''leaf'' is a vertex with no children.{{sfn|Bender|Williamson|2010|p=173}} An ''internal vertex'' is a vertex that is not a leaf.{{sfn|Bender|Williamson|2010|p=173}}

The ''height'' of a vertex in a rooted tree is the length of the longest downward path to a leaf from that vertex. The ''height'' of the tree is the height of the root. The ''depth'' of a vertex is the length of the path to its root (''root path''). The depth of a tree is the maximum depth of any vertex. Depth is commonly needed in the manipulation of the various self-balancing trees, [[AVL tree]]s in particular. The root has depth zero, leaves have height zero, and a tree with only a single vertex (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (a tree with no vertices, if such are allowed) has depth and height −1.

A ''[[k-ary tree|{{mvar|k}}-ary tree]]'' (for nonnegative integers {{mvar|k}}) is a rooted tree in which each vertex has at most {{mvar|k}} children.<ref>See {{cite web|url=http://xlinux.nist.gov/dads/HTML/karyTree.html|title=k-ary tree|last=Black|first=Paul E.|date=4 May 2007|publisher=U.S. National Institute of Standards and Technology|access-date=8 February 2015|archive-date=8 February 2015|archive-url=https://web.archive.org/web/20150208124845/http://xlinux.nist.gov/dads/HTML/karyTree.html|url-status=live}}</ref> 2-ary trees are often called ''[[binary tree]]s'', while 3-ary trees are sometimes called ''[[ternary tree]]s''.