Basic Terminology of tree

Here’s a clear overview of the basic terminology of trees in computer science and data structures:

1. Tree

A tree is a hierarchical data structure consisting of nodes, with one special node called the root, and zero or more child nodes for each parent node. Trees are used to represent hierarchical relationships like file systems, organizational charts, and decision processes.

2. Node

A node is an individual element of a tree that contains data and links to child nodes.

3. Root

The root is the topmost node of a tree. It has no parent. Every tree has exactly one root.

4. Parent

A parent is a node that has one or more children.

5. Child

A child is a node that has a parent node.

6. Leaf (External Node)

A leaf is a node that has no children.

7. Internal Node

An internal node is any node that is not a leaf, i.e., it has at least one child.

8. Sibling

Nodes that share the same parent are called siblings.

9. Degree

  • Degree of a node: The number of children a node has.

  • Degree of a tree: The maximum degree of any node in the tree.

10. Path

A path is a sequence of nodes and edges connecting a node with a descendant.

11. Height / Depth

  • Depth of a node: Number of edges from the root to the node.

  • Height of a node: Number of edges from the node to the deepest leaf.

  • Height of a tree: Height of the root node.

12. Subtree

A subtree is a tree formed by a node and all its descendants.

13. Edge

An edge is the connection between a parent node and a child node.

14. Forest

A forest is a collection of disjoint trees.