Tree Terminology
- Tree
-
A hierarchical data structure composed of nodes where each node has at most one parent and zero or more children.
- Root
-
The starting node at the top of the tree.
- Parent
-
A node that has children.
- Child
-
A node directly connected to a parent node.
- Sibling
-
Nodes that share the same parent.
- Degree
-
The degree of a node is the total number of its children, while the degree of a tree is the maximum degree found among all its nodes.
- Leaf Node
-
A node that has no children. A leaf, by definition, has degree zero.
- Internal Node
-
A node that has at least one child.
- Empty Tree
-
A tree that contains no nodes.
- Edge
-
The connection or link between two nodes, also known as a branch.
- Subtree
-
A node in a tree together with all of its descendants and the edges connecting them, forming a smaller tree structure within the larger one.
- Path
-
A sequence of successive edges from a starting node to an ending node.
- Ancestor
-
An ancestor of a node is any node above it on the path that leads all the way from the root of the tree down to the specific node in question.
- Descendant
-
A descendant of a node is any node below it along a path leading away from the root, which includes its children, grandchildren, and so on.
- Level
-
The level of a node in a tree is the length of the path (number of edges) from the root node to that specific node. The root node is at level zero.
- Height
-
The height of a tree is the length of the longest path (number of edges) from the root node to any leaf node in the tree. It is equivalent to the maximum level found among all of its leaf nodes.
- Binary Tree
-
A tree data structure where the maximum degree of any node is two, meaning every node can have at most two children, referred to as the left child and the right child.
- Binary Search Tree (BST)
-
A specific binary tree where for every node, all values in its left subtree are less than its value, and all values in its right subtree are greater than its value.
- Full Tree
-
A tree in which every node has either zero children or as many children as the tree’s degree.
- Complete Tree
-
A tree where every level, except possibly the last, is completely filled, and all nodes at the last level are filled from left to right.
- Perfect Tree
-
A full tree where all the leaves are at the same level. The number of nodes \(N\) in a perfect binary tree of height \(H\) is:
$$
N = 2^{H+1} − 1
$$
References