Trees in a nutshell
A tree is a non-linear data structure that organizes data hierarchically in nodes and cannot contain cycles. A tree has a specific terminology that may vary slightly, but commonly, the following notions are adopted:
- Root is the topmost node.
- Edge is the link or connection between two nodes.
- Parent is a node that has an edge to a child node.
- Child is a node that has a parent node.
- Leaf is a node that does not have a child node.
- Height is the length of the longest path to a leaf.
- Depth is the length of the path to its root.
The following diagram exemplifies these terms when used on a tree:
Figure 13.1 – Tree terminology
Typically, any tree can have a root. The nodes of the tree can respect a certain order (or not), can store any type of data, and may have links to their parents.
Tree coding challenges are rife with ambiguous details and/or incorrect assumptions. It is very important to clarify...
