[Binary Tree]

[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();
    // 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

/* In-order traversal */
void InOrder(TreeNode? root) {
    if (root == null) return;
    // Visit priority: left subtree -> root node -> right subtree

/* Post-order traversal */
void PostOrder(TreeNode? root) {
    if (root == null) return;
    // Visit priority: left subtree -> right subtree -> root node

Pre-order: root-left-right, in-order: left-root-right, post-order: left-right-root.


Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.