Think of a family tree: a line from a parent to a child tells you how two people are related. In a data-structure tree, that connection is a link between nodes. If node P links to node C, P is C’s parent and C is P’s child. section 11.2
A tree’s root has no parent. Every other node has exactly one parent, so there is only one path from the root to any given node. A node with no links to children is a leaf. Some trees also store links back from children to parents to make traversal easier. section 11.2 section 11.2
Follow the links
Suppose a root has links to nodes containing 2 and 8. Those nodes are its children and are siblings, but there is no direct link between them. To travel from one sibling to the other, go through their common parent. section 11.2
A tree link is a particular kind of graph edge: graphs connect vertices with edges, and trees are connected graphs without cycles. A general graph can express relationships that do not form a parent–child hierarchy, such as social-network friendships. section 13.16 section 13.3
In a binary tree, child links are usually labeled left and right. In a binary search tree, that distinction guides where values belong: values in the left subtree are no greater than the parent’s value, while those in the right subtree are greater. section 11.20 section 11.20
