[Binary tree] is a non-linear data structure that represents the derived relationship between ancestors and descendants, reflecting the "divide and conquer" logic of "dividing into two parts".
The basic unit of a binary tree is a node, each node has a value, a reference to the [left child node], and a reference to the [right child node].
class TreeNode {
int val;
TreeNode? left;
TreeNode? right;
TreeNode(int x) => val = x;
}
In a binary tree, except for leaf nodes, all other nodes contain child nodes and non-empty subtrees (trees formed by child nodes and their descendants).
Common terms of binary trees#
- [Root node]: The top-level node that has no parent node.
- [Leaf node]: A node that does not have any child nodes.
- [Edge]: A line segment that connects two nodes, i.e., a node reference (pointer).
- [Level]: The level at which a node is located, increasing from top to bottom, with the root node at level 1.
- [Degree]: The number of child nodes a node has. In a binary tree, the degree can be 0, 1, or 2.
- [Height]: The number of edges from the root node to the farthest leaf node.
- [Depth]: The number of edges from the root node to the given node.
- [Height]: The number of edges from the farthest leaf node to the given node.
💡 Please note that "height" and "depth" are usually defined as the "number of edges traversed".
Common types of binary trees#
1. [Perfect binary tree]#
All levels, except the bottom level, are completely filled with nodes.
2. [Complete binary tree]#
Only the nodes in the bottom level are not completely filled, and they are filled from left to right as much as possible.
3. [Full binary tree]#
Except for the leaf nodes, all other nodes have two child nodes.
4. [Balanced binary tree]#
The absolute difference between the heights of the left and right subtrees of any node is not more than 1.
Binary tree traversal#
[Level-order traversal]#
[Level-order traversal] traverses the binary tree from top to bottom, layer by layer, and visits the nodes in each layer from left to right.
Level-order traversal essentially belongs to [breadth-first traversal] and reflects the "expanding outward in circles" layer-by-layer traversal method.
Breadth-first traversal is usually implemented using a "queue".
/* Level-order traversal */
List<int> LevelOrder(TreeNode root) {
// Initialize the queue and add the root node
Queue<TreeNode> queue = new();
queue.Enqueue(root);
// Initialize a list to store the traversal sequence
List<int> list = new();
while (queue.Count != 0) {
TreeNode node = queue.Dequeue(); // Dequeue from the queue
list.Add(node.val); // Save the node value
if (node.left != null)
queue.Enqueue(node.left); // Enqueue the left child node
if (node.right != null)
queue.Enqueue(node.right); // Enqueue the right child node
}
return list;
}
Pre-order, in-order, and post-order traversal#
Pre-order, in-order, and post-order traversal all belong to [depth-first traversal], which represents a "go to the end and then backtrack" traversal method.
Depth-first traversal is like "walking" around the entire binary tree's periphery, encountering three positions at each node, corresponding to pre-order traversal, in-order traversal, and post-order traversal.
Depth-first traversal is usually implemented using recursion.
/* Pre-order traversal */
void PreOrder(TreeNode? root) {
if (root == null) return;
// Visit priority: root node -> left subtree -> right subtree
list.Add(root.val);
PreOrder(root.left);
PreOrder(root.right);
}
/* In-order traversal */
void InOrder(TreeNode? root) {
if (root == null) return;
// Visit priority: left subtree -> root node -> right subtree
InOrder(root.left);
list.Add(root.val);
InOrder(root.right);
}
/* Post-order traversal */
void PostOrder(TreeNode? root) {
if (root == null) return;
// Visit priority: left subtree -> right subtree -> root node
PostOrder(root.left);
PostOrder(root.right);
list.Add(root.val);
}
Mnemonic:
Pre-order: root-left-right, in-order: left-root-right, post-order: left-right-root.