root (of a tree)

\\xyoption

all

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.)

\\xymatrix{&{\\color[rgb]{1,0,0}\\bullet}\\ar@{-}[dl]\\ar@{-}[dr]&&&\\inner@par%\\bullet&&\\bullet\\ar@{-}[dr]\\ar@{-}[dl]&&\\inner@par&\\bullet\\ar@{-}[dl]&&\\bullet%&\\inner@par\\bullet&&&&}

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 tree, 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 reachable from that node by following the arrows between them in the proper direction.