Tree Data Structure
- Only one node is the root node (root does not have an incoming edge/link).
- Every other node is connected by a directed edge from exactly one other node. The node connected by a directed edge is the child node and the node where the link comes from is the parent node.
- Every node can have any number of children.
- If a node B has a path from node A, then A is called ancestor and B is called descendant.
- Nodes without any children is called leaf node (external node).
- Nodes with at least one child is called internal node.
- Set of nodes that have edges coming in from same node are called siblings.
- The number of edges from the root to a node is called the depth of the node.
- The number of edges from the root node to the deepest leaf node is the height of the tree.
- A set of nodes and edges that are connecting a node with its descendants is called as the path. The length of a path is 1 less than the number of nodes on that path.
- The number of children that a node has is called as degree of that node.
- A node B of a tree with all of its descendants is called as sub-tree with B as its root node.