Fundamentals of Tree Structures

Before we explore specific tree-based algorithms like Binary Search Trees or Decision Trees, let's establish a common vocabulary for discussing tree structures themselves. At its core, a tree is a collection of entities called nodes linked together by connections called edges, representing a hierarchical relationship. Unlike linear structures like arrays or linked lists, trees are non-linear.

Think of a family tree or an organization chart; these are everyday examples of tree structures. In computer science, trees provide an efficient way to store data that has an inherent hierarchy or needs to be rapidly searched or sorted.

Terminology

Here are the essential terms you'll encounter when working with trees:

• Node: The fundamental part of a tree. It contains data and may link to other nodes.
• Edge: The connection or link between two nodes. If an edge exists between node A and node B, A might be the parent and B the child, or vice versa.
• Root: The single, topmost node in a tree. It's the only node that has no incoming edges (no parent). Every tree has exactly one root.
• Parent: A node that has an edge connecting to a node below it in the hierarchy. A node can have only one parent. The root node has no parent.
• Child: A node that has an edge connecting from a node above it. A node can have zero, one, or multiple children.
• Siblings: Nodes that share the same parent.
• Leaf (or External Node): A node with no children. These are the nodes at the bottom extremities of the tree.
• Internal Node: Any node that has at least one child (i.e., any node that is not a leaf).
• Subtree: A portion of a tree consisting of a node and all its descendants. It is itself a valid tree, rooted at that node.

Measuring Trees: Depth, Height, and Levels

We often need to describe the size and shape of trees:

• Depth of a Node: The number of edges on the path from the root to that node. The depth of the root node is 0.
• Height of a Node: The number of edges on the longest path from that node down to a leaf in its subtree. The height of a leaf node is 0.
• Height of a Tree: The height of its root node. This represents the length of the longest path from the root to any leaf.
• Level: Often used interchangeably with depth. Nodes at the same depth are said to be at the same level. The root is at level 0, its children are at level 1, and so on.

Let's visualize these terms:

A diagram illustrating tree terminology. Node A is the root. Nodes B and C are children of A and are siblings. Nodes E, F, and G are leaves (external nodes). Nodes A, B, C, and D are internal nodes. The subtree rooted at B includes nodes B, D, E, and G. The height of the tree is 3 (longest path: A -> B -> D -> G). Node D is at depth 2 and has a height of 1.

Types of Trees

While there are many specialized tree structures (like heaps, covered later), a foundational type is the Binary Tree. In a binary tree, each node can have at most two children, typically referred to as the left child and the right child.

This constraint is simple but powerful. It forms the basis for Binary Search Trees (BSTs), which allow for efficient searching, insertion, and deletion (often $O(\log n)$ time on average, where $n$ is the number of nodes), and Decision Trees used in machine learning models. We will explore these specific applications in the following sections.

Understanding this basic structure and terminology is the first step toward leveraging trees effectively for organizing data and building machine learning models. The hierarchical nature allows for partitioning data or decisions, while properties like height directly relate to the potential efficiency (or inefficiency) of tree operations.