Skip to content

Tree Terminology

Understanding the terminology associated with trees is essential to effectively work with and understand tree data structures. Here’s a breakdown of the most important terms:

Basic Components

  1. Node:
    1. A basic unit of a tree containing data and links to its child nodes.
    1. Every node consists of:
      1. Key: The value or data stored in the node.
      1. Pointer(s): References to its child nodes.
  2. Edge:
    1. A connection between two nodes.
    1. Represents the relationship between a parent and a child.
  3. Root:
    1. The top-most node of the tree.
    1. It has no parent.
  4. Leaf:
    1. A node with no children.
    1. Also called a terminal node.
  5. Parent:
    1. A node that has one or more children.
  6. Child:
    1. A node directly connected and below a parent.
  7. Subtree:
    1. A tree formed by any node and its descendants.

Structural Relationships

  1. Siblings:
    1. Nodes that share the same parent.
  2. Ancestor:
    1. A node is an ancestor of another node if there is a path from the ancestor to the node.
    1. Example: In a binary tree, the root is an ancestor of all other nodes.
  3. Descendant:
    1. A node is a descendant of another node if it lies below that node in the tree.

Tree Metrics

  1. Degree:
    1. The number of children a node has.
    1. The degree of a tree is the maximum degree of any node in the tree.
  2. Level:
    1. The depth of a node in the tree.
    1. The root is at level 0, its children are at level 1, and so on.
  3. Height:
    1. The length of the longest path from a node to a leaf.
    1. The height of the tree is the height of the root.
  4. Depth:
    1. The length of the path from the root to a particular node.
    1. Depth of the root is 0.
  5. Path:
    1. A sequence of nodes and edges connecting a node to another node.
  6. Degree of a Tree:
    1. The maximum degree of any node in the entire tree.

Tree Traversal

Traversal is not part of the core terminology but is essential for understanding how nodes are visited:

  • In-order Traversal: Visit left subtree, root, then right subtree.
  • Pre-order Traversal: Visit root, then left and right subtrees.
  • Post-order Traversal: Visit left subtree, right subtree, then root.
  • Level-order Traversal: Visit nodes level by level.

Special Nodes in a Tree

  1. Internal Node:
    1. A node that has at least one child.
    1. It is not a leaf.
  2. External Node:
    1. Synonymous with a leaf node, having no children.
  3. Root Node:
    1. The starting point of the tree, with no parent.
  4. Terminal Node:
    1. Another term for a leaf node.

Tree Types Based on Terminology

  1. Full Tree: Every internal node has exactly the maximum number of children.
  2. Complete Tree: All levels, except possibly the last, are fully filled.
  3. Balanced Tree: The height difference between the left and right subtrees of any node is minimal.

Example

For the following tree:

mathematica

Copy code

        A

      /   \

     B     C

    / \   / \

   D   E F   G

  • Root: A
  • Internal Nodes: A, B, C
  • Leaf Nodes: D, E, F, G
  • Parent of B: A
  • Children of B: D, E
  • Siblings of E: D
  • Height of the Tree: 2
  • Level of E: 2
  • Path from Root to G: A → C → G

This structured understanding allows for easier implementation and manipulation of tree data structures.