Binary Tree Basic and Common Types

labuladongOriginalAbout 2462 words

Prerequisites

Before reading this article, you need to study:

Basics of Linked Lists (Linked Storage)

I believe the binary tree is the most important fundamental data structure, bar none.

If you are a beginner, it might be difficult for me to thoroughly explain why I arrived at this conclusion at this stage. You need to carefully study the subsequent content on this site to gradually understand. For now, I will summarize two points:

The binary tree itself is a relatively simple fundamental data structure, but many complex data structures are based on binary trees, such as Red-Black Trees (binary search trees), Multi-way Trees, Binary Heaps, Graphs, Tries, Union-Find, Segment Trees, etc. Once you master binary trees, these data structures become manageable; if you don't understand binary trees, these advanced data structures will be difficult to handle.
Binary trees not only represent a data structure but also embody a recursive mindset. All recursive algorithms, such as Backtracking Algorithms, BFS Algorithms, Dynamic Programming, essentially abstract specific problems into a tree structure. Once you abstract them, these problems ultimately revert to binary tree issues. When you look at a piece of algorithm code, it may appear as a string of text to others, but in your eyes, the code is a tree, and you can modify it correctly with ease.

The subsequent chapters on data structures contain extensive explanations and exercises on binary trees. By following the site's directory order, I will help you thoroughly understand binary trees, and then you will understand why I emphasize them so much.

Common Types of Binary Trees

The main challenge of binary trees is in solving algorithm problems; the structure itself is not difficult to understand, as it is just a tree-like structure:

Above is a simple binary tree, and here are some terms you need to know:

Nodes directly connected below a node are called child nodes, and nodes directly connected above are called parent nodes. For example, node 3's parent is 1, its left child is 5, and right child is 6. Node 5's parent is 3, its left child is 7, and it has no right child.
A tree with a child node as its root is called a subtree. For example, node 3's left subtree consists of nodes 5 and 7, and its right subtree consists of nodes 6 and 8.
We refer to the topmost node without a parent as the root node, and the bottommost nodes without children, such as 4, 7, and 8, as leaf nodes.
The number of nodes from the root node to the furthest leaf node is the maximum depth/height of the binary tree. The maximum depth of the tree above is 4, which is the number of nodes on the path from root 1 to leaf nodes 7 or 8.

That's all there is to it, it's quite simple.

There are some slightly specialized binary trees with their own names that you should be aware of, so when you encounter these terms in problems, you'll understand what they refer to.

Perfect Binary Tree

It's intuitive to look at the diagram directly; a perfect binary tree is where every level is fully filled, and the entire tree resembles an equilateral triangle:

The advantage of a perfect binary tree is that the number of nodes is easy to calculate. Assuming the depth is h, the total number of nodes is 2^h - 1, derived from a geometric series sum, which we should be familiar with.

Complete Binary Tree

A complete binary tree is one where every level of the tree is compactly arranged to the left, and except for the last level, all other levels must be full:

It is not difficult to see that a perfect binary tree is actually a special kind of complete binary tree.

Characteristics of a complete binary tree: Its nodes are compactly arranged, and if numbered from left to right, top to bottom, there is a clear pattern to the parent-child node indices.

This characteristic is used in explaining Core Principles of Binary Heap and Core Principles of Segment Tree: a complete binary tree can be stored using an array, without the need to actually construct linked nodes.

A less obvious property of complete binary trees is: The left and right subtrees of a complete binary tree are also complete binary trees.

More accurately, at least one of the subtrees of a complete binary tree is a perfect binary tree.

This property is useful in solving algorithm problems, such as Counting Nodes in a Complete Binary Tree, mentioned here briefly.

Differences in Definitions Between Chinese and English

Regarding the definitions of complete and perfect binary trees, there seems to be a slight difference between the Chinese and English contexts.

The complete binary tree we refer to corresponds to the English "Complete Binary Tree," which is correct, referring to the same type of tree.

What we call a perfect binary tree should theoretically translate to "Full Binary Tree," but it is not; the definition of a perfect binary tree corresponds to the English "Perfect Binary Tree."

In English, a "Full Binary Tree" refers to a binary tree where every node has either no children or two children.

These definitions are from Wikipedia, just for reference. Essentially, it doesn't matter what the terms are called; knowing there is a difference is enough, so be aware when reading English materials.

Binary Search Tree

A Binary Search Tree (BST) is a common type of binary tree defined as follows:

For each node in the tree, the value of every node in its left subtree must be less than the value of that node, and the value of every node in its right subtree must be greater. You can simply remember this as "left smaller, right larger."

I emphasized "every node in the subtree" because beginners often make the mistake of focusing only on child nodes rather than all nodes in the entire subtree.

For example, the following is a BST:

All node values in the left subtree of node 7 are less than 7, and all node values in the right subtree are greater than 7. Similarly, all node values in the left subtree of node 4 are less than 4, and all node values in the right subtree are greater than 4.

Conversely, the following tree is not a BST:

If you only focus on each node's left and right children, you might not see the issue. However, you should consider the entire subtree; note that there's a node 8 in the left subtree of node 7, which is greater than 7, violating the BST definition.

BST is a highly useful data structure. Its "left smaller, right larger" property allows quick location of a specific node or all nodes within a range, which is the advantage of a BST.

For instance, in an ordinary binary tree with no specific order among nodes, finding a node with value x requires a full traversal starting from the root.

In a BST, you can compare the root node with x. If x is greater than the root node, you can immediately exclude the entire left subtree and start searching in the right subtree, quickly locating the node with value x.

There will be a dedicated chapter with detailed explanations and numerous exercises on BSTs later, but for now, these basic concepts will suffice.

Balanced Binary Tree

A Balanced Binary Tree is a special type of binary tree where the height difference between the left and right subtrees of "every node" does not exceed 1.

It is important to note that this applies to every node, not just the root node.

For example, in the binary tree below, the left subtree height of the root node 1 is 2, and the right subtree height is 3; node 2 has a left subtree height of 1 and a right subtree height of 0; node 3 has a left subtree height of 2 and a right subtree height of 1. Consequently, the height difference between the left and right subtrees of every node does not exceed 1, making it a balanced binary tree:

The following tree is not a balanced binary tree because node 2 has a left subtree height of 2 and a right subtree height of 0, with a height difference exceeding 1, thus not meeting the criteria:

Assuming there are $N$ nodes in a balanced binary tree, the height of the balanced binary tree is $O(\log N)$ . This is a crucial property because several tree-based data structures discussed in subsequent sections can achieve high efficiency in insertion, deletion, search, and update operations if the tree height remains $O(\log N)$ .

Conversely, if the tree is significantly unbalanced, as in this extreme case:

This tree essentially becomes equivalent to a singly linked list, resulting in a significant reduction in the efficiency of operations like insertion, deletion, search, and update.

Self-Balancing Binary Tree

As previously described, a balanced binary tree has a height of $O(\log N)$ , leading to high efficiency in operations.

Therefore, we can perform some structural adjustments to the tree during node insertion and deletion to maintain its balance. There are various types of self-balancing binary trees, with the most classic being the Red-Black Tree, a type of self-balancing binary search tree.

The key to maintaining tree balance is the "rotation" operation. The following visual panel demonstrates the rotation operations of a Red-Black Tree. You can click the code for left and right rotations to observe the effects:

Algorithm Visualization

Implementation of Binary Trees

The most common binary tree is similar to a linked list, using a linked storage structure where each binary tree node has pointers to its left and right child nodes. This method is straightforward and intuitive.

On LeetCode, the binary trees you are given as input are generally constructed using this method. The TreeNode class for binary tree nodes typically looks like this:

java 🟢

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { this.val = x; }
}

// You can construct a binary tree like this:
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.right.left = new TreeNode(5);
root.right.right = new TreeNode(6);

// The constructed binary tree looks like this:
//     1
//    / \
//   2   3
//  /   / \
// 4   5   6

cpp 🤖

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// You can construct a binary tree like this:
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->right->left = new TreeNode(5);
root->right->right = new TreeNode(6);

// The constructed binary tree is like this:
//     1
//    / \
//   2   3
//  /   / \
// 4   5   6

python 🤖

class TreeNode:
    def __init__(self, x: int):
        self.val = x
        self.left = None
        self.right = None

# You can build a binary tree like this:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)

# The constructed binary tree looks like this:
#     1
#    / \
#   2   3
#  /   / \
# 4   5   6

go 🤖

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// You can construct a binary tree like this:
root := &TreeNode{Val: 1}
root.Left := &TreeNode{Val: 2}
root.Right := &TreeNode{Val: 3}
root.Left.Left := &TreeNode{Val: 4}
root.Right.Left := &TreeNode{Val: 5}
root.Right.Right := &TreeNode{Val: 6}

// The constructed binary tree looks like this:
//     1
//    / \
//   2   3
//  /   / \
// 4   5   6

javascript 🤖

var TreeNode = function(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}

// you can construct a binary tree like this:
var root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.right.left = new TreeNode(5);
root.right.right = new TreeNode(6);

// the constructed binary tree looks like this:
//     1
//    / \
//   2   3
//  /   / \
// 4   5   6

Since the above is a common implementation method, it implies there are other methods, right?

Yes, in Principles and Implementation of Binary Heap and Detailed Explanation of Union-Find Algorithm, we choose to use arrays to store binary trees based on specific needs.

When visualizing recursive functions in the Visualization Panel, a recursive tree is generated from the function stack, which can also be considered a way to implement binary trees.

Moreover, in typical algorithm problems, we may abstract the real-world problem into a binary tree structure, but we don't necessarily need to create a binary tree using TreeNode. Instead, we can represent binary/multi-way trees using structures similar to a hash table.

For example, consider the binary tree above:

I can use a hash table where the keys are parent node ids and the values are lists of child node ids (each node's id is unique). A key-value pair represents a multi-way tree node, and this multi-way tree can be represented as:

java 🟢

// 1 -> [2, 3]
// 2 -> [4]
// 3 -> [5, 6]

HashMap<Integer, List<Integer>> tree = new HashMap<>();
tree.put(1, Arrays.asList(2, 3));
tree.put(2, Collections.singletonList(4));
tree.put(3, Arrays.asList(5, 6));

cpp 🤖

// 1 -> {2, 3}
// 2 -> {4}
// 3 -> {5, 6}

unordered_map<int, vector<int>> tree;
tree[1] = {2, 3};
tree[2] = {4};
tree[3] = {5, 6};

python 🤖

# 1 -> [2, 3]
# 2 -> [4]
# 3 -> [5, 6]

tree = {
    1: [2, 3],
    2: [4],
    3: [5, 6]
}

go 🤖

// 1 -> [2, 3]
// 2 -> [4]
// 3 -> [5, 6]

tree := map[int][]int{
    1: {2, 3},
    2: {4},
    3: {5, 6},
}

javascript 🤖

// 1 -> [2, 3]
// 2 -> [4]
// 3 -> [5, 6]

let tree = new Map([
    [1, [2, 3]],
    [2, [4]],
    [3, [5, 6]]
]);

This way, you can simulate and manipulate binary tree/multi-way tree structures. When we discuss graph theory later, you will learn that it has a new name called Adjacency List.