A tree is a hierarchical collection of nodes or vertices connected by edges. Trees cannot have cycles, and only edges will exist between a node and its descended nodes or child nodes. Two child nodes of a same parent cannot have any edges in between them. Each node can have a parent other than the top node, which is also known as the root node. There can be only one root node per tree. Each node can have zero or more child nodes. In the following diagram, A is the root node, and B, C, and D are the child nodes of A. We can also say that A is the parent node of B, C, and D. B, C, and D are known as siblings as they are child nodes from the same parent, A:
The node that does not have any children is known as a leaf. In the preceding diagram, K, L, F, G, M, I, and J are leaf nodes. Leaf nodes are also known as external nodes or terminal nodes. A node, other than the root, having at least one child, is known as an internal node. Here, B, C, D, E, and H are internal nodes. Here are some other common terms we use when describing tree data structure:
- Descendent: This is a node that can be reached from a parent node by repeated proceedings. For example, M is a descendent of C in the previous diagram.
- Ancestor: This is a node that can be reached from a child node to a parent node by a repeated way. For example, B is the ancestor of L.
- Degree: The total number of child nodes of a particular parent node is known as its degree. In our example, A has degree 3, B has degree 1, C has degree 3, and D has degree 2.
- Path: The sequence of nodes and edges from a source node to a target node is known as the path between two nodes. The length of the path is the number of nodes in the path. In our example, the path between A to M is A-C-H-M, and the length of the path is 4:
- Height of node: The height of a node is defined by the number of edges between the node and the deepest level of the descendent node. For example, the height of node B is 2.
- Level: The level represents the generation of nodes. If a parent node is in level n, its child node will be in the n+1 level. So, the level is defined by 1+ number of edges between the node and the root. Here:
-
- Root A is in Level 0
- B, C, and D are in Level 1
- E, F, G, H, I, and J are in Level 2
- K, L, and M are in Level 3
- Height of tree: The height of a tree is defined by the height of its root node. Here, the height of the tree is 3.
- Subtree: In a tree structure, each child forms a subtree recursively. In other words, a tree consists of many subtrees. For example, B forms a subtree with E, K, and L, whereas E forms a subtree with K and L. In the preceding example, we have identified each in the left-hand side in different shades. We can do the same for C and D and their subtrees as well.
- Depth: The depth of a node is determined by the number of edges between the node and the root node. For example, in our tree image, the depth of H is 2 and the depth of L is 3.
- Forest: A forest is a set of zero or more disjoint trees.
- Traverse: This indicates the process of visiting nodes in a specific order. We will use this term often in the upcoming sections.
- Keys: A key is a value from the node that is used for searching purposes.