Mastering Binary Tree Traversals: BFS vs. DFS in C++
Binary Tree Basics
The Structure of a Binary Tree
A binary tree is a hierarchical data structure where each node has at most two children. Think of it like a family tree, but with a strict rule: each parent can have a maximum of two offspring. This simple constraint makes binary trees incredibly efficient for certain tasks, especially searching and sorting data.
Unlike arrays or linked lists, which are linear, trees are non-linear, allowing for more complex relationships between data elements.
The fundamental unit of a tree is the node. Each node contains a piece of data (its value) and pointers, or references, to its children. Because it's a binary tree, these pointers are specifically for a left child and a right child. If a child doesn't exist, its pointer is null.
Key Terminology
To work with trees, we need a shared vocabulary. Most terms are intuitive and build on the family tree analogy.
| Term | Definition |
|---|---|
| Root | The single topmost node in the tree. It's the only node with no parent. |
| Parent | A node that has at least one child node. |
| Child | A node that has a parent. Every node except the root is a child. |
| Leaf | A node with no children. These are the endpoints of the tree. |
| Internal Node | A node that is not a leaf; it has at least one child. |
| Edge | The link or connection between a parent and its child. |
| Subtree | A node and all of its descendants. A subtree is itself a valid binary tree. |
The distinction between a left and right child is important. In many applications, the position indicates a specific relationship to the parent's data. For example, a left subtree might contain values less than the parent, while the right subtree contains values that are greater.
Tree Properties
Beyond the basic structure, we can classify binary trees by their properties. These classifications help us analyze their efficiency and choose the right type of tree for a specific problem.
Height
noun
The number of edges on the longest path from a node to a leaf. The height of the entire tree is the height of its root node.
Depth
noun
The number of edges from the root to a specific node. The depth of the root is 0.
Height and depth are related but distinct. Height is a property of the tree (or a subtree), looking down from a node. Depth is a property of a single node, looking from the root down to it.
Now, let's look at a few special types of binary trees.
Full Binary Tree: Every node has either zero or two children. No node has only one child.
Complete Binary Tree: Every level is completely filled, except possibly the last level. The last level must be filled from left to right.
Perfect Binary Tree: A tree that is both full and has all its leaves at the same depth.
Why do these properties matter? A complete binary tree is particularly useful because its structure is predictable. This allows it to be stored efficiently in an array, which is the foundation of the heap data structure.
Understanding these basic definitions and properties is the first step. Next, we'll explore how to navigate, or traverse, these trees to access the data they hold.