Binary Tree Basic and Common Types

labuladongOriginalAbout 2024 words

Prerequisite Knowledge

Before reading this article, you should first study:

Basics of Linked Lists (Linked Storage)

In my opinion, binary trees are the most important fundamental data structure, bar none.

If you are a beginner, it might be challenging for me to fully explain the reasons behind this conclusion at this stage. You need to seriously study the following content on this site to gradually understand. For now, let me summarize two points:

The binary tree itself is a relatively simple fundamental data structure, but many complex data structures are built upon it, such as red-black trees (binary search trees), multi-way trees, binary heaps, graphs, trie, disjoint set union, and segment trees, among others. Once you understand binary trees, these structures become manageable; if not, these advanced structures will be difficult to handle.
A binary tree is not just a data structure; it also represents a recursive way of thinking. All recursive algorithms, such as backtracking, BFS, and dynamic programming, essentially abstract specific problems into a tree structure. Once abstracted, these problems ultimately simplify to binary tree problems. When you look at an algorithm's code, it may seem like a string of text to others, but to you, it's a tree. You can modify it as you wish, and you will do it correctly. It's just that simple.

The subsequent sections on data structures contain extensive explanations and exercises on binary trees. By following the site's content order, I will guide you in thoroughly understanding binary trees, and you'll see why I emphasize them so much.

Common Types of Binary Trees

The main challenge with binary trees lies in solving algorithm problems. The structure itself is not particularly difficult; it's just a tree-like form:

Above is a simple binary tree, and there are a few terminologies you should be familiar with:

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

There's not much else to say—it's that straightforward.

There are some special types of binary trees with unique names. Familiarize yourself with these terms so you'll understand what a problem is referring to when you encounter them later.

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.