Tree Terminology (Root, Node, Leaf, Depth, Height)
Introduction to Trees: Essential Terminology
Welcome to the world of Trees, a fundamental non-linear data structure that models hierarchical relationships. Unlike linear structures like arrays or linked lists, trees branch out, allowing for efficient organization and retrieval of data in many applications. Before diving into specific tree types and operations, it's crucial to understand the foundational terminology that describes their components and structure.
1. Core Components of a Tree
Imagine a family tree or an organizational chart; these are real-world examples of tree structures.
- Node: The fundamental unit of a tree. Each node typically contains a value or data and may have references (pointers) to other nodes.
- Edge: The link or connection between two nodes. Edges represent the relationship between nodes.
- Root: The topmost node in a tree. It's unique and has no parent. Every other node in the tree can be reached from the root.
- Parent: A node that has one or more child nodes connected to it.
- Child: A node directly connected to another node when moving away from the root.
- Sibling: Nodes that share the same parent.
- Leaf Node: A node that has no children. These are at the "bottom" of the tree's branches.
- Internal Node: Any node that is not a leaf node (i.e., it has at least one child).
2. Understanding Tree Structure: Depth, Level, and Height
These terms help us describe the vertical arrangement and size of a tree.
-
Depth of a Node: The number of edges from the root node to that specific node. The root node has a depth of 0.
- Example: In a tree, if the root is at depth 0, its direct children are at depth 1, their children at depth 2, and so on.
-
Level of a Node: Often used interchangeably with depth, or sometimes defined as
depth + 1(so the root is at Level 1). We will primarily use "depth" for consistency. -
Height of a Node: The number of edges on the longest path from that node down to a leaf node. A leaf node has a height of 0.
-
Height of a Tree: The height of its root node. This is equivalent to the maximum depth of any node in the tree.
Example Tree Structure: A (Root, Depth 0, Height 2) / \ B C (Depth 1, Height 1) / \ D E (Depth 2, Height 0 - Leaves) - Height of node A is 2 (path A -> B -> D or A -> B -> E) - Height of node B is 1 (path B -> D or B -> E) - Height of node D is 0 - Height of the tree is 2 (height of the root A)
3. Paths and Relationships
- Path: A sequence of nodes connected by edges. For example, in the tree above, A -> B -> D is a path.
- Ancestor: A node
Ais an ancestor of nodeBifAis on the path from the root toB. (The root is an ancestor of all nodes). - Descendant: A node
Bis a descendant of nodeAifAis an ancestor ofB. (All nodes are descendants of the root). - Subtree: A portion of a tree that itself forms a tree. Any node in a tree can be considered the root of a subtree consisting of itself and all its descendants.
Key Takeaway: Mastering tree terminology is the first step to understanding and working with tree data structures. These terms provide a precise language for discussing tree properties, which is essential for designing and analyzing tree-based algorithms.