This is a beta course, so its structure, chapters, and examples may continue to change.

Trees and Binary Trees

A tree is an important non-linear data structure: directory structures, organizational charts, expression evaluation and data compression can all be modelled with trees. A binary tree is the special form of a tree, and it is the absolute focus of the algorithm examinations: the traversals, the threading and the Huffman coding are all high-frequency examination points. This chapter starts from the basic concepts of a tree, goes deeper into the characteristics, the storage and the traversals of a binary tree, and finally introduces the conversion between trees and forests together with the typical applications. After reading this section you will be able to understand the basic concepts, the terminology and the properties of a tree, master the definition, the properties and the special binary trees of a binary tree, master the sequential and the linked storage structures of a binary tree, master the pre-order, in-order, post-order and level-order traversals as well as the construction of a binary tree from its traversal sequences, understand the threaded binary tree and the storage and the conversion of trees and forests, and master the applications of the binary search tree, of the balanced binary tree and of the Huffman tree.

Questions This Chapter Answers

How can the one-to-many hierarchical relationship be stored and traversed efficiently? A binary tree is an ordered tree in which “every node has at most two children”, so how it is stored sequentially or in linked form, how it is traversed in the four ways of pre-order, in-order, post-order and level-order, and how it is restored from a traversal sequence are all core questions. In addition, how a threaded binary tree speeds itself up with the null pointers, how trees and forests are converted into each other, and how a Huffman tree builds an optimal code all have to be sorted out one by one.

Basic route: basic concepts → storage structures → traversals; master the definition, the storage and the four traversals of a binary tree first.

Advanced route: threaded binary trees, trees and forests → applications → summary; understand the advanced characteristics of a tree structure and their practical value.

The property of a binary tree

n_0 = n_2 + 1

, the unique determination of a binary tree by the “pre-order + in-order” or the “post-order + in-order” pair, and the construction of a Huffman code are the three most frequently examined points of this chapter, so be sure to master them through the exercises. The conclusion that the in-order traversal of a BST yields a sorted sequence also has to be remembered.

Basic Concepts of Trees and Binary Trees

A tree (Tree) is a finite set of n (with $n \ge 0$ ) nodes. When n = 0 it is an empty tree. In any non-empty tree:

There is exactly one root node
The remaining nodes can be divided into m (with $m > 0$ ) mutually disjoint finite sets $T_1, T_2, \ldots, T_m$ , each of which is itself a tree, called a subtree of the root

Common Terminology of a Tree

Degree of a node: the number of subtrees that the node has
Degree of a tree: the largest degree among all the nodes of the tree
Leaf node (terminal node): a node whose degree is 0
Branch node (non-terminal node): a node whose degree is greater than 0
Level: the root is at level 1, the children of the root are at level 2, and so on
Depth (height): the largest level number of a node
Forest: a set of m (with $m \ge 0$ ) mutually disjoint trees

Properties of a Tree

The number of nodes in a tree equals the sum of the degrees of all the nodes plus 1
In a tree of degree m, the i-th level holds at most $m^{i-1}$ nodes (for $i \ge 1$ )
An m-ary tree of depth h holds at most $\frac{m^h-1}{m-1}$ nodes

The Definition of a Binary Tree

A binary tree (Binary Tree) is a finite set of n (with $n \ge 0$ ) nodes in which every node has at most two children (a left child and a right child), and in which the left and the right subtrees have a strict order that cannot be reversed.

Properties of a Binary Tree

The i-th level of a non-empty binary tree holds at most $2^{i-1}$ nodes
A binary tree of depth h holds at most $2^h-1$ nodes
In any binary tree the number of the leaf nodes $n_0$ and the number of the nodes of degree 2 $n_2$ satisfy: $n_0 = n_2 + 1$
The depth of a complete binary tree with n nodes is $\lfloor \log_2 n \rfloor + 1$

Property 3 (

n_0 = n_2 + 1

) is a conclusion that the 408 exam asks for very often. Proof: let the total number of nodes be n, then

n = n_0 + n_1 + n_2

; also

n = B + 1

(where B is the number of the branch nodes) and

B = n_1 + 2n_2

, and combining the two gives

n_0 = n_2 + 1

Special Binary Trees

Full binary tree: every level reaches the largest possible number of nodes and all the leaves are on the bottom level
Complete binary tree: every level but the last one is full, and the nodes of the last level are packed against the left in consecutive positions
Binary search tree (BST): the value of every node in the left subtree is smaller than the root and the value of every node in the right subtree is greater than the root
Balanced binary tree (AVL): the difference between the heights of the left and the right subtree of any node is at most 1

Exercises

Exercise 1

In a binary tree the number of the nodes of degree 2 is 5, then the number of the leaf nodes is ( )

A. 4 B. 5 C. 6 D. Cannot be determined

Reference Answer

binary treeleaf nodenode degreeproperty derivation

Approach:

This question tests the property that relates the node degrees of a binary tree. The idea is to recall the relation $n_0 = n_2 + 1$ between the numbers of the nodes of degree 0, 1 and 2 in a binary tree, and to substitute the given number of the nodes of degree 2 in order to obtain the number of the leaf nodes.

Steps:

Let the numbers of the nodes of degree 0, 1 and 2 in a binary tree be $n_0$ , $n_1$ and $n_2$ ; counting the degrees of the nodes gives the property $n_0 = n_2 + 1$ .
The question gives the number of the nodes of degree 2 as $n_2 = 5$ .
Substituting it gives the number of the leaf nodes $n_0 = 5 + 1 = 6$ , which corresponds to option C.

Answer:

C (6).

Exercise 2

Briefly describe the main differences between a tree and a binary tree.

Reference Answer

treebinary treeorderinglogical structure

Approach:

This question tests the main differences between a tree and a binary tree. In the answer, compare them from two angles, whether the number of the children is restricted and whether the subtrees are distinguished as left and right, and in particular clarify that a binary tree is not a special case of a tree in the number of the children.

Steps:

A tree: every node may have any number of children, and the subtrees of a node are not distinguished as left and right, that is, they are unordered.
A binary tree: every node has at most two children (a left one and a right one), and the left and the right subtrees have a strict order that cannot be reversed.
The key clarification: a binary tree is not a special case of a tree in the number of the children, but rather an independent structure of its own, because it introduces the extra constraint of the left and the right order.

Answer:

A tree: every node may have any number of children, and the subtrees of a node are not distinguished as left and right (they are unordered). A binary tree: every node has at most two children (a left one and a right one), and the left and the right subtrees have a strict order that cannot be reversed. A binary tree is not a special case of a tree but an independent structure of its own.

Storage Structures

Sequential Storage

A complete binary tree is stored in an array: the root node is stored at index 1, the left child of the node i is 2i, the right child is 2i+1 and the parent is $\lfloor i/2 \rfloor$ . This suits a complete binary tree, while an ordinary binary tree wastes a great deal of space.

Linked Storage

Every node has a data field, a left pointer and a right pointer:

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;  // pointers to the left and the right child
} BiTNode, *BiTree;

Exercises

Exercise 1

How can a complete binary tree be stored in an array?

Reference Answer

complete binary treesequential storageindex relationlinked storage

Approach:

This question tests the array storage of a complete binary tree. The idea is to make use of the fact that the nodes of a complete binary tree are numbered consecutively, to express the positions of the left child, the right child and the parent of a node directly with index arithmetic, and then to compare that with the trade-off of the storage methods for an ordinary binary tree.

Steps:

Store a complete binary tree in a one-dimensional array in index order, with the root node stored at index 1.
By the numbering rule of a complete binary tree, the left child of any node $i$ is at index $2i$ , the right child is at index $2i+1$ and the parent is at index $\lfloor i/2 \rfloor$ .
Because the nodes of a complete binary tree are stored in the array one after another, the indices from 1 to n correspond to all the nodes, so the sequential storage wastes no space.
The nodes of an ordinary binary tree may leave a great many gaps in the array, so the sequential storage wastes a great deal of space and the linked storage is the better choice.

Answer:

Store a complete binary tree in a one-dimensional array in index order: the root node is stored at index 1, the left child of any node i is 2i, the right child is 2i+1 and the parent is $\lfloor i/2 \rfloor$ . A complete binary tree suits the sequential storage and wastes no space, while an ordinary binary tree wastes a great deal of space in the sequential storage and is better stored in the linked form.

Threaded Binary Trees, Trees and Forests

Threaded Binary Trees

The many null pointers of a binary tree (a binary tree with n nodes has n+1 null pointers) are used to store the predecessor and the successor information of a traversal, which improves the efficiency of the traversal.

Predecessor thread: a null left pointer points at the predecessor in the traversal sequence
Successor thread: a null right pointer points at the successor in the traversal sequence
A flag bit has to be added in order to tell a child pointer from a thread pointer

The Storage Structures of a Tree

Parent representation: the nodes are stored in an array together with the index of their parent, so the parent is found in $O(1)$ time while the children have to be found by a traversal
Child representation: every node stores its children in a linked list, so the children are easy to find while the parent has to be found by a traversal
Child-sibling representation: every node has two pointers, one to its first child and one to its right sibling, and it can be converted into a binary tree

The Conversion Between a Forest and a Binary Tree

Tree → binary tree: left child, right sibling; the children of a node become its left subtree and its siblings become its right subtree
Forest → binary tree: first convert every tree of the forest into a binary tree, and then make the root of the next tree the right child of the root of the previous one

Exercises

Exercise 1

What is the purpose of a threaded binary tree?

Reference Answer

threaded binary treenull pointerpredecessor and successorin-order traversal

Approach:

This question tests the purpose of a threaded binary tree. The idea is to point out first that the number of the null pointers of a binary tree is exactly the number of the predecessor and successor pieces of information that a traversal sequence needs, and then to explain the two benefits that come from storing that information in the null pointers.

Steps:

A binary tree with $n$ nodes has $n+1$ null pointers in total, and the predecessor and successor information that has to be recorded in a traversal sequence is exactly as much as these null pointers can hold.
A threaded binary tree fills the corresponding null pointers with the predecessor and the successor information of the traversal sequence, so that a node carries its threads without any change to the structure.
Two benefits follow from this: the traversal can be performed efficiently without recursion and without a stack, and the speed of the traversal is improved while the extra stack space is saved.

Answer:

A threaded binary tree uses the null pointers of a binary tree (a binary tree with n nodes has n+1 null pointers) to store the predecessor and the successor information of a traversal sequence, so that the traversal can be performed efficiently without recursion and without a stack, which improves the speed of the traversal and saves space.

Binary Tree Traversals

Three Depth-First Traversals (Recursive)

Pre-order traversal (root, left, right): visit the root first, then traverse the left subtree, and finally traverse the right subtree
In-order traversal (left, root, right): traverse the left subtree first, then visit the root, and finally traverse the right subtree
Post-order traversal (left, right, root): traverse the left subtree first, then traverse the right subtree, and finally visit the root

// pre-order traversal
void PreOrder(BiTree T) {
    if (T != NULL) {
        visit(T);            // visit the root node
        PreOrder(T->lchild); // traverse the left subtree
        PreOrder(T->rchild); // traverse the right subtree
    }
}

// in-order traversal
void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

// post-order traversal
void PostOrder(BiTree T) {
    if (T != NULL) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

Time complexity: $O(n)$ (every node is visited once). Space complexity: $O(n)$ in the worst case (the depth of the recursion stack equals the height of the tree, and the worst case is a chain).

Level-Order Traversal

The nodes are visited layer by layer from the top down and from the left to the right, which needs a queue:

void LevelOrder(BiTree T) {
    InitQueue(Q);
    EnQueue(Q, T);
    while (!QueueEmpty(Q)) {
        DeQueue(Q, p);
        visit(p);
        if (p->lchild != NULL) EnQueue(Q, p->lchild);
        if (p->rchild != NULL) EnQueue(Q, p->rchild);
    }
}

Constructing a Binary Tree from Its Traversal Sequences

Pre-order + in-order: the pre-order sequence fixes the root, the in-order sequence splits the left and the right subtrees, and the tree is built recursively
Post-order + in-order: the post-order sequence fixes the root (the last one), the in-order sequence splits the left and the right subtrees, and the tree is built recursively
Pre-order + post-order: a binary tree cannot be determined uniquely

Exercises

Exercise 1

The pre-order traversal sequence of a binary tree is A, B, C and its post-order traversal sequence is C, B, A, then its in-order traversal sequence is ( )

A. A, B, C B. C, B, A C. B, A, C D. Cannot be determined uniquely

Reference Answer

binary tree traversalpre-order traversalpost-order traversalin-order traversal

Approach:

This question tests whether a binary tree can be determined uniquely from the pre-order and the post-order sequences. The key is that neither of these two traversals can determine on its own which nodes belong to the two subtrees of the root, so the position of the root in the in-order sequence has to be used to split the left and the right subtrees; without the in-order sequence the answer is not unique.

Steps:

The first element of the pre-order sequence is the root and the last element of the post-order sequence is the root, so the two agree and the root is A.
But the pre-order and the post-order sequences only give the orders root-left-right and left-right-root, and they cannot tell whether the remaining B and C belong to the left subtree or to the right subtree.
For example, when BC is the left subtree of A the in-order sequence is B, C, A; when BC is the right subtree of A the in-order sequence is A, B, C.
Two different binary trees are consistent with the given pre-order and post-order sequences, so the tree cannot be determined uniquely.

Answer:

Exercise 2

The in-order traversal sequence of a binary tree is JGDHKBAELIMCF and its post-order traversal sequence is JGKHDBLMIEFCA, then its pre-order traversal sequence is ( )

A. ABDGHJKCEFILM B. ABDGJHKCEILMF C. ABDHKGJCEILMF D. ABDGJHKCEIMLF

Reference Answer

binary tree traversalin-order traversalpost-order traversalpre-order traversal

Approach:

The in-order and the post-order sequences are given here and the pre-order sequence is asked for. The idea is to use the rule “the last element of the post-order sequence is the root, and the position of the root in the in-order sequence cuts the sequence into a left half and a right half” again and again, to determine every subtree recursively, and then to concatenate the pre-order sequences of the subtrees.

Steps:

Step 1: determine the root. The last element of the post-order traversal is the root of the whole tree, that is A.
Step 2: split the left and the right subtrees with the in-order sequence. The in-order traversal is JGDHKB | A | ELIMCF, so the in-order of the left subtree is JGDHKB and the in-order of the right subtree is ELIMCF.
Step 3: build the left subtree recursively. After the root A is removed from the post-order sequence, the part of the left subtree is JGKHDB, whose last element B is the root of the left subtree; in the in-order JGDHKB of the left subtree nothing stands to the right of B, so B has no right subtree and what stands to the left of B is JGDHK. Continuing: JGDHK corresponds to the post-order JGKHD, its root is D, and in the in-order sequence JG stands to the left of D and HK to its right; JG corresponds to the post-order JG, its root is G, and J stands to the right of G in the in-order sequence, so G has no left child and its right child is J, which gives ABDGJ in the pre-order; HK corresponds to the post-order KH, its root is H, and K stands to the left of H in the in-order sequence, so H has K as its left child and no right child, and appending it gives ABDGJHK in the pre-order.
Step 4: build the right subtree recursively. The post-order of the right subtree is LMIEFC, whose last element C is the root of the right subtree; in the in-order ELIMCF of the right subtree nothing stands to the right of C and ELIMF stands to its left. ELIMF corresponds to the post-order LMIEF, its root is F, in the in-order sequence E stands to the right of F and LIM to its left; LIM corresponds to the post-order LMI, its root is I, L stands to the left of I and M to its right in the in-order sequence, which gives CEILM when it is appended to the pre-order; finally the right child of F is E, which gives CEILMF in the pre-order.
Step 5: combine the pre-order sequences. The pre-order traversal = root + the pre-order of the left subtree + the pre-order of the right subtree = A + BDGJHK + CEILMF = ABDGJHKCEILMF, which is option B.

Answer:

B (ABDGJHKCEILMF).

Exercise 3

What are the visiting orders of the pre-order, the in-order and the post-order traversals of a binary tree?

Reference Answer

pre-order traversalin-order traversalpost-order traversalbinary tree traversal

Approach:

This question tests the visiting orders of the three depth-first traversals of a binary tree. The idea is to grasp the one and only difference between them, namely the moment at which the root node is visited; the rest of them all consist in traversing the left subtree and then the right subtree recursively.

Steps:

The pre-order traversal (root, left, right): visit the root node first, then traverse the left subtree, and finally traverse the right subtree.
The in-order traversal (left, root, right): traverse the left subtree first, then visit the root node, and finally traverse the right subtree.
The post-order traversal (left, right, root): traverse the left subtree first, then traverse the right subtree, and finally visit the root node.
The only difference between the three is the moment at which the root node is visited: the pre-order visits the root first, the in-order visits it in the middle and the post-order visits it last.

Answer:

Pre-order (root, left, right): visit the root first, then traverse the left subtree, and finally traverse the right subtree. In-order (left, root, right): traverse the left subtree first, then visit the root, and finally traverse the right subtree. Post-order (left, right, root): traverse the left subtree first, then traverse the right subtree, and finally visit the root. The difference between the three lies in the moment at which the root node is visited: the pre-order visits the root first, the in-order in the middle and the post-order last.

Applications

Binary Search Tree (BST)

The left subtree is smaller than the root and the right subtree is greater than it. Searching, inserting and deleting take $O(\log n)$ on average. The in-order traversal of a BST yields a sorted sequence.

Balanced Binary Tree (AVL)

The difference between the heights of the left and the right subtree of any node (the balance factor) is at most 1. After an insertion or a deletion the balance is restored by a rotation (LL, RR, LR, RL), which keeps the efficiency of the search at $O(\log n)$ .

Huffman Trees and Huffman Coding

Huffman tree (optimal binary tree): the binary tree with the smallest weighted path length (WPL)
Construction method: every time the two nodes with the smallest weights are merged, until only one tree is left
Huffman coding: 0 for the left branch and 1 for the right branch, used for data compression (a prefix code, without ambiguity)

Exercises

Exercise 1

(A real problem of the 408 exam in 2023) In a character set S made up of 6 characters, the frequencies of the characters are 3, 4, 5, 6, 8 and 10, then the weighted average length of the Huffman code built for S is ( )

A. 2.4 B. 2.5 C. 2.67 D. 2.75

Reference Answer

Huffman treeHuffman codingweighted path lengthoptimal prefix code

Approach:

This question asks for the weighted average length of a Huffman code. The idea is to build the Huffman tree bottom up with the Huffman algorithm first, then to obtain the weighted path length WPL from the code length of every character in the tree, and finally to divide it by the total frequency to get the weighted average length.

Steps:

Sort the frequencies in ascending order: 3, 4, 5, 6, 8, 10.
Take the two smallest frequencies 3 and 4 and merge them into a new node whose weight is 7; the remaining frequencies are 5, 6, 7, 8, 10.
Take the two smallest 5 and 6 and merge them into a new node whose weight is 11; the remaining frequencies are 7, 8, 10, 11.
Take the two smallest 7 and 8 and merge them into a new node whose weight is 15; the remaining frequencies are 10, 11, 15.
Take the two smallest 10 and 11 and merge them into a new node whose weight is 21; the remaining frequencies are 15, 21.
Finally merge 15 and 21 into the root node, whose weight is 36.
Read the code length of every character off the tree: the frequencies 10 and 8 have a code length of 2, and the frequencies 6, 5, 4 and 3 have a code length of 3.
Compute the weighted path length: WPL = (10 × 2) + (8 × 2) + (6 × 3) + (5 × 3) + (4 × 3) + (3 × 3) = 20 + 16 + 18 + 15 + 12 + 9 = 90.
The weighted average length = WPL / the total frequency = 90 / (3+4+5+6+8+10) = 90 / 36 = 2.5.

Answer:

B (2.5).

Exercise 2

What is the main application of a Huffman tree?

Reference Answer

Huffman treeHuffman codingoptimal prefix codedata compression

Approach:

This question tests the main application of a Huffman tree. In the answer, first point out that the core application is the Huffman coding, that is, the optimal prefix code, then explain why it can compress the data and why the decoding is unambiguous, and finally add that it can also be used to build an optimal decision tree.

Steps:

The main application of a Huffman tree is the Huffman coding, that is, the optimal prefix code, which is used for data compression.
The coding strategy gives the characters of a high frequency a short code and the characters of a low frequency a long one, so that the total length of the codes is the shortest possible.
Because the code of no character is the prefix of the code of another character, the decoding process is unambiguous and the original text can be restored uniquely.
In addition, a Huffman tree can be used to build an optimal decision tree.

Answer:

The main application of a Huffman tree is the Huffman coding (the optimal prefix code), which is used for data compression. The characters of a high frequency are given a short code and the characters of a low frequency a long one, so that the total length of the codes is the shortest possible. Because the code of no character is the prefix of the code of another character, the decoding is unambiguous. In addition it can be used to build an optimal decision tree.

Summary

Trees and binary trees are the chapter with the highest density of concepts in the whole of data structures: the properties, the traversals, the threading and the Huffman tree can each become an examination question on their own. The terminology table aligns the terms full binary tree, complete binary tree, the four traversals and threaded binary tree with their English names, and the key takeaways give the $n_0 = n_2 + 1$ relation and the upper bound on the number of nodes per level that have to be remembered; the remaining concepts are best reviewed together with the traversal demonstrations of this chapter.

Terminology Reference

Term	Abbreviation	Explanation
Tree	-	A finite set of n nodes
Binary tree	-	An ordered tree in which every node has at most two children
Leaf node	Leaf	A node whose degree is 0
Depth	-	The largest level number of a node
Full binary tree	-	The number of the nodes reaches its maximum on every level
Complete binary tree	-	The nodes of the last level are packed against the left
Pre-order traversal	Preorder	Root, left, right
In-order traversal	Inorder	Left, root, right
Post-order traversal	Postorder	Left, right, root
Level-order traversal	Level-order	Traversing layer by layer
Threaded binary tree	-	Using the null pointers to store the predecessors and the successors
Huffman tree	-	The binary tree with the smallest weighted path length

Key Takeaways

The properties of a binary tree: $n_0 = n_2 + 1$ ; the i-th level holds at most $2^{i-1}$ nodes
The pre-order + in-order pair or the post-order + in-order pair determines a binary tree uniquely; the pre-order + post-order pair does not
The recursive code of the three traversals only changes the position of the visit call, and their time complexities are all $O(n)$
The level-order traversal is implemented with a queue
Huffman coding is the optimal prefix code and is used for data compression

Arrays and Special Matrices

Graphs

Found an issue with this content?

Tell us what could be improved.

Your membership covers this course — no need to buy it again.

Login Required to Purchase

Payment Failed

Payment Successful!

Trees and Binary Trees

Questions This Chapter Answers

Basic Concepts of Trees and Binary Trees

Common Terminology of a Tree

Properties of a Tree

The Definition of a Binary Tree

Properties of a Binary Tree

Special Binary Trees

Exercises

Exercise 1

Exercise 2

Storage Structures

Sequential Storage

Linked Storage

Exercises

Exercise 1

Threaded Binary Trees, Trees and Forests

Threaded Binary Trees

The Storage Structures of a Tree

The Conversion Between a Forest and a Binary Tree

Exercises

Exercise 1

Binary Tree Traversals

Three Depth-First Traversals (Recursive)

Level-Order Traversal

Constructing a Binary Tree from Its Traversal Sequences

Exercises

Exercise 1

Exercise 2

Exercise 3

Applications

Binary Search Tree (BST)

Balanced Binary Tree (AVL)

Huffman Trees and Huffman Coding

Exercises

Exercise 1

Exercise 2

Summary

Terminology Reference

Key Takeaways