"Rooted tree terminology\n\nRooted trees carry with them a number of terms. I’ll use the tree on the left side of Figure 5.16 as an illustration of each:\n\nroot. The node at the top of the tree, which is A in our example. Note that unlike trees in the real world, computer science trees have their root at the top and grow down. Every tree has a root except the empty tree, which is the “tree” that has no nodes at all in it. (It’s kind of weird thinking of “nothing” as a tree, but it’s kind of like the empty set ∅, which is still a set.)\n\nparent. Every node except the root has one parent: the node immediately above it. D’s parent is C, C’s parent is B, F’s parent is A, and A has no parent.\n\nchild. Some nodes have children, which are nodes connected directly below it. A’s children are F and B, C’s are D and E, B’s only child is C, and E has no children.\n\nsibling. A node with the same parent. E’s sibling is D, B’s is F, and none of the other nodes have siblings.\n\nancestor. Your parent, grandparent, great-grandparent, etc., all the way back to the root. B’s only ancestor is A, while E’s ancestors are C, B, and A. Note that F is not C’s ancestor, even though it’s above it on the diagram: there’s no connection from C to F, except back through the root (which doesn’t count).\n\ndescendant. Your children, grandchildren, great-grandchildren, etc., all the way to the leaves. B’s descendants are C, D and E, while A’s are F, B, C, D, and E.\n\nleaf. A node with no children. F, D, and E are leaves. Note that in a (very) small tree, the root could itself be a leaf.\n\ninternal node. Any node that’s not a leaf. A, B, and C are the internal nodes in our example.\n\ndepth (of a node). A node’s depth is the distance (in number of nodes) from it to the root. The root itself has depth zero. In our example, B is of depth 1, E is of depth 3, and A is of depth 0.\n\nheight (of a tree). A rooted tree’s height is the maximum depth of any of its nodes; i.e., the maximum distance from the root to any node. Our example has a height of 3, since the “deepest” nodes are D and E, each with a depth of 3. A tree with just one node is considered to have a height of 0. Bizarrely, but to be consistent, we’ll say that the empty tree has height -1! Strange, but what else could it be? To say it has height 0 seems inconsistent with a one-node tree also having height 0."