A Plain-Language Introduction to Binary Trees

March 12 is a national holiday: 植树节 . While I never planted a tree at work, I have learned many 树的结构 such as binary trees, B+ trees, and red‑black trees, which are common interview topics. To celebrate Tree‑Planting Day, I will first explain what a binary tree is before moving on to B‑trees in a future article.

Plain-Language Explanation of Binary Trees

Suppose we have an array of many user names and need to find a specific name quickly. We would think of binary search, which is fast only if the array is sorted. If we keep the array sorted upon insertion, the resulting structure is an ordered one.

Someone therefore designed a data structure called a 二叉查找树 , also known as a 二叉树 (binary search tree).

Below is an illustration of a binary tree:

Assume "Herry" is the root, with children Alice, Mike, Ivy, and Tom arranged left‑to‑right. The in‑order traversal yields Alice → Herry → Ivy → Mike → Tom, which is alphabetical.

The diagram introduces four terms: node, left child, right child, and root. Red circles represent nodes; a node’s left‑down connection is the left child, and the right connection is the right child. The root is the single topmost node (Herry in the picture).

For each node, the left child’s value is smaller and the right child’s value is larger (e.g., Alice < Herry < Mike).

To find "Ivy", we start at the root, see that Ivy > Herry, move to the right child Mike, then because Ivy < Mike we go to Mike’s left child and find Ivy.

Searching in a binary search tree has average time O(log n) and worst‑case O(n). In a sorted array, binary search also has worst‑case O(log n). Although binary search may seem faster, binary trees offer much faster insertion and deletion. The following chart compares the two:

Binary trees also have drawbacks:

They do not support random access; you cannot directly retrieve the 10th element as you can with an array.

They can become unbalanced, e.g., when the right subtree contains many more nodes than the left, leading to poor search performance.

Balanced binary trees do exist, such as red‑black trees, which will be covered in a later article.

Meaning of Binary Trees

Definition

In simple terms, a binary tree is a structure where each node has at most two subtrees, designated as left and right.

Formally, a binary tree is a finite set of n (n ≥ 0) nodes that is either empty (the empty binary tree) or consists of a root node together with two disjoint subtrees called the left and right subtrees.

Five Forms of Binary Trees

Empty binary tree.

A single‑node tree (only the root).

Tree with only a left subtree.

Tree with only a right subtree.

Complete binary tree.

Node Degree

The degree of a node is the number of its child subtrees.

For example, node B has degree 2, node E has degree 1, and the degree of the tree is the maximum node degree, which is 2.

Node Levels

The root is at level 1, its children at level 2, and so on.

Characteristics of Binary Trees

Each node has at most two children, so no node has degree greater than 2.

The left and right subtrees have a defined order; they cannot be swapped arbitrarily.

Even if a node has only one subtree, it must be identified as either left or right.

Binary Tree Traversal

Traversal means starting from the root and visiting every node exactly once in a specific order.

There are four common traversal orders:

Pre‑order traversal.

In‑order traversal.

Post‑order traversal.

Level‑order traversal.

Pre‑order : Visit the node when it is first encountered, then recursively visit the left subtree followed by the right subtree.

In‑order : Visit the node after the left subtree has been visited, then the right subtree.

Post‑order : Visit the node after both left and right subtrees have been visited.

Level‑order : Visit nodes level by level from top to bottom.

For the example tree, the traversal results are:

Pre‑order: BADCE

In‑order: ABCDE

Post‑order: ACEDB

Level‑order: BADCE

Reference: "Algorithms Illustrated" (https://www.jianshu.com/p/bf73c8d50dc2)