Binary Tree Basic and Common Types

labuladongOriginalAbout 2014 words

Prerequisite Knowledge

Before reading this article, you need to learn:

Basics of Linked Lists (Linked Storage)

I believe the binary tree is the most important basic data structure, without a doubt.

If you're a beginner, it might be challenging to fully understand why I make this claim at this stage. You will gradually comprehend it as you continue to study the materials on this site. For now, I'll summarize two points:

The binary tree itself is a relatively simple basic data structure, but many complex data structures are based on it, such as Red-Black Trees (Binary Search Trees), Multi-way Trees, Binary Heaps, Graphs, Trie Trees, Disjoint Set Union, Segment Trees, etc. Once you master the binary tree, these structures will not pose a problem; if you do not, these advanced structures will be difficult to handle.
The binary tree is not merely a data structure; it represents a recursive way of thinking. All recursive algorithms, such as Backtracking, BFS, Dynamic Programming, essentially abstract specific problems into a tree structure. Once you achieve this abstraction, these problems ultimately revert to binary tree problems. When you look at a piece of algorithm code, while others may see a string of text that seems incomprehensible, you see it as a tree, easily modifiable and always correct, making it incredibly simple.

The subsequent chapters on data structures include extensive explanations and exercises on binary trees. By following the site's learning path, I will guide you to thoroughly understand binary trees, and then you will understand why I emphasize them so much.

Common Types of Binary Trees

The main challenge with binary trees lies in solving algorithmic problems. In essence, they are just a tree-like structure:

The above is a simple binary tree, and there are a few terms you should be familiar with:

Nodes directly connected below a given node are called child nodes, and those directly connected above are called parent nodes. For example, the parent node of 3 is 1, with 5 as its left child and 6 as its right child; the parent node of 5 is 3, with 7 as its left child and no right child.
The topmost node without a parent, 1, is called the root node, and the lowest nodes without children, 4, 7, 8, are called leaf nodes.
The number of nodes from the root node to the lowest leaf node is referred to as the maximum depth/height of the binary tree. The maximum depth of the tree above is 4, which is the number of nodes from the root 1 to leaf nodes 7 or 8.

That's about it. It's quite straightforward.

There are some slightly more specialized binary trees with their own names. Familiarizing yourself with these terms will help when you encounter them in problem statements.

Perfect Binary Tree

Visualizing it directly with a diagram, a perfect binary tree is one where every level is fully filled, and the entire tree resembles an equilateral triangle:

Perfect binary trees have the advantage of a simple node count. If the depth is h, then the total number of nodes is 2^h - 1, which is a sum of a geometric series—a concept we are all familiar with.

Complete Binary Tree

A complete binary tree is one where all levels are fully filled except possibly the last, and all nodes are as far left as possible:

It is easy to see that a perfect binary tree is a special case of a complete binary tree.

A characteristic of complete binary trees is that their nodes are compactly arranged, and if we number the nodes from left to right, top to bottom, there is a clear pattern in the indices of parent and child nodes.

This characteristic will be specifically discussed when we talk about Binary Heap Principles and Implementation, and it is also useful in solving algorithm problems.

Another less obvious property of complete binary trees is that: the left and right subtrees of a complete binary tree are also complete binary trees.

Or more precisely: at least one of the subtrees of a complete binary tree is a perfect binary tree.

This property is useful in algorithm problems, such as Calculating the Number of Nodes in a Complete Binary Tree. This is just an introduction.

Differences in Definitions Between Chinese and English

There seems to be a difference in the definitions of complete binary trees and perfect binary trees between Chinese and English contexts.

In Chinese, a complete binary tree corresponds to the English "Complete Binary Tree," which is the same concept.

However, what is referred to as a perfect binary tree in Chinese is actually translated as "Perfect Binary Tree" in English.

In English, a "Full Binary Tree" means a binary tree where every node has either zero or two children.

The above definitions are from Wikipedia, mentioned here for reference. The terminology is not crucial as long as you are aware of the differences, especially 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 is less than the value of the node, and the value of every node in its right subtree is greater than the value of the node. Simply put, "left small, right large."

I've emphasized "every node in the subtree" because beginners often make the mistake of only looking at the child nodes. You need to consider all nodes in the entire subtree.

For example, the following tree is a BST:

The value of all nodes in the left subtree of node 7 is less than 7, and the value of all nodes in the right subtree is greater than 7. Similarly, the value of all nodes in the left subtree of node 4 is less than 4, and the value of all nodes in the right subtree is greater than 4, and so on.

Conversely, the following tree is not a BST:

If you only look at each node's left and right children, you might not see the problem. You should look at the entire subtree. Notice that node 7's left subtree contains a node 8, which is greater than 7, thus violating the BST definition.

BSTs are very commonly used data structures. Because of the "left small, right large" property, we can quickly find a particular node or all nodes within a specific range in a BST. This is the advantage of a BST.

For instance, in a regular binary tree where node values have no specific order, finding a node with value x requires traversing the entire tree starting from the root node.

In a BST, you can compare the root node's value with x. If x is greater than the root node's value, you can immediately exclude the entire left subtree and start searching from the right subtree, allowing you to quickly locate the node with value x.

We will cover BSTs in detail in later chapters, with plenty of exercises. For now, these basic concepts should suffice.

Implementing Binary Trees

The most common binary tree structure is similar to a linked list, where each binary tree node has pointers to its left and right children. This method is simple and intuitive.

On platforms like LeetCode, the binary trees you are given are usually constructed in this way. A typical TreeNode class for a binary tree node 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 that there are other implementation 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 scenarios.

When visualizing recursive functions in the Visualization Panel, a recursive tree is generated from the function stack, which can be considered a form of binary tree implementation.

Additionally, in general algorithm problems, we might abstract the actual problem into a binary tree structure, but we don't need to create a binary tree with TreeNode. Instead, we use structures like Hash Tables to represent binary/multi-way trees directly.

For example, the binary tree above:

We can use a hash table where the keys are parent node IDs, and the values are lists of child node IDs (each node has a unique ID). Thus, a key-value pair represents a multi-way tree node, and the multi-way tree can be represented like this:

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.