root (of a tree)



The root of a tree is a place-holder node. It is typically drawn at the top of the page, with the other nodes below (with all nodes having the same path distance from the root at the same height.)


Figure: A tree with root highlighted in red.

Any tree can be redrawn this way, selecting any node as the root. This is important to note: taken as a graph in general, the notion of “root” is meaningless. We introduce a root explicitly when we begin speaking of a graph as a tree– there is nothing in general that selects a root for us.

However, there are some special cases of trees where the root can be distinguished from the other nodes implicitly due to the properties of the tree. For instance, a root is uniquely identifiable in a complete binary treeMathworldPlanetmathPlanetmath, where it is the only node with degree two.

Further, in a directed tree, there can be only one root. This is because all nodes must be reachablePlanetmathPlanetmath from that node by following the arrows between them in the proper direction.

Title root (of a tree)
Canonical name RootofATree
Date of creation 2013-03-22 12:30:11
Last modified on 2013-03-22 12:30:11
Owner akrowne (2)
Last modified by akrowne (2)
Numerical id 8
Author akrowne (2)
Entry type Definition
Classification msc 05C05
Synonym root