Algorithms: Sequential, Parallel and Distributed 4-1
Chapter 4
Trees and Applications to Algorithms
At a Glance
Table of Contents
• Overview
• Objectives
• Instructor Notes
• Solutions to Selected Exercises
Algorithms: Sequential, Parallel and Distributed 4-2
Lecture Notes
Overview
In Chapter 4 we discuss trees and their applications to algorithms. Trees play many important
roles in both the design and analysis of algorithms. We begin the chapter by reviewing
definitions relating to binary trees and general trees. We then discuss mathematical properties
of binary trees and 2-trees, proving various lower bound results about the depth and leaf path
length. We then review the classical implementations of binary trees and general trees such as
the array implementation of the complete binary tree, the left-right child implementation of a
Chapter Objectives
After completing the chapter the student will know:
• Basic definitions relating to binary trees, trees and forests
• Mathematical properties of binary trees and 2-trees relating to depth and leaf-path
length
• Implementations of trees and forests: array implementation of the complete binary tree,
the left-right child implementation of a binary tree, the child-sibling representation of a
general tree and the parent representation of trees and forests
• Traversals of trees: preorder, inorder, postorder
• The binary search tree ADT and it application to the dictionary problem and treesort
• The heap ADT and its application to priority queues and heapsort
• The disjoint set ADT and algorithms Union and Find. Also, the collapsing rule and the
algorithm Find
Instructor Notes
Binary search trees will be revisited again in Chapter 10 of Part II in the discussion optimal
binary search trees. While most students will be familiar with the tree ADT, they probably
will not be familiar with the mathematical properties of trees. Thus, the instructor should make
Algorithms: Sequential, Parallel and Distributed 4-3
Solutions to Selected Exercises
Section 4.2 Mathematical Properties of Binary Trees
4.1 Assume to the contrary that T is not full at some level less than i, and let j be the largest
4.2 Let k be the integer such that 2k – 1 < n ≤ 2k+1 – 1, so that k =
n
2
log
. The full tree Tk on
n
log
2
4.3 This exercise is the same as the previous one, except we will now use induction to prove the
result.
n
log
2
4.5 We wish to show that I(T) = L(T) – 1. We prove this by induction of the number I(T) of
internal nodes.
Basis step: A 2-tree with no internal nodes (the 2-tree on one node) has one leaf node, that
is, the root node.
4.6 We prove Proposition 4.2.4 by using (the strong form) of induction on the number of leaf
nodes.
Basis step: A tree with one leaf node (the root itself in a one node tree) has depth 0 =
1log 2
.
Induction step: Assume true for all binary trees having less than k leaf nodes and consider a
binary tree T having k leaf nodes. Let T’ be the tree obtained from T by removing all leaf
nodes at the deepest level. Since the parents of these leaf nodes in T become leaf nodes in
T’, and since each such parent has at most 2 children, it follows that T’ has at least k/2 leaf
nodes, i.e., L(T’) ≥ k/2. Clearly, the depth of T’ is one less than the depth of T, that is,
d(T’) = d(T) – 1. (1)
By the induction hypothesis we have that
d(T’) ≥
)(log 2TL
≥
2/log 2k
≥
k
2
log
– 1. (2)
Combining Formulas (1) and (2) we obtain
d(T) = d(T’) + 1 ≥ (
k
2
log
– 1) + 1 =
k
2
log
.
4.7 We are to prove that a 2-tree T is full at the second-deepest level if, and only if, all the leaf
nodes are contained in two levels d – 1 and d, where d is the depth of T.
4.8 Suppose T is a 2-tree that is full at the second-deepest level d – 1, where d = d(T) is the
depth of T. Since each node at level d-1 is either a leaf or has two children, it follows that
4.9 We prove the formula IPL(T) = LPL(T) – 2I by induction on the number of internal nodes I
of the 2-tree T.
Basis step: If I = 1, then IPL(T) = 0 = 2 – 2*1 = LPL(T) – 2I.
Induction step: Assume that the formula holds for all 2-trees with I internal nodes, and let T
¯ obtained from T by deleting the
¯) =
IPL(T
It follows that
IPL(T) = LPL(T) – 2I, completing the induction.
4.10 We will show that
)2(2log 2
log
2
x
xxx −+
≥
xx 2
log
for any real number x ≥ 1. We
log
x
2
xx 2
log
holds we use calculus to show that the function f(x) = 2(x – 1) –
xx 2
log
has no local
minima. Solving for
0loglog2)( 2=−−=
xxxf e
, we obtain a local maximum at 4 – e.
Thus, the minimum value in the interval 1 ≤ x ≤ 2 occurs at one of the boundaries, i.e., x = 1
or x = 2. Since f(1) = f(2) = 0, it follows that f(x) ≥ 0 for all x in the interval 1 ≤ x ≤ 2.
Thus, we have shown that 2(x – 1) ≥
xx 2
log
completing the basis step.
)2(2log 2
log
2
x
xxx −+
≥
xx 2
log
,
completing the induction step.
log
2
x
)2(2log 2
xxx −+
log
2
x
4.11 a) LPL(T) = LPL(Tleft) + LPL(Tright) + L
b) We will show that
LLTLPL 2
log)(
using the strong form of induction on the
number L of leaf nodes.
Induction step: Now suppose the result is true for all binary trees with fewer than L leaf nodes
4.12 We prove that the implicit search tree T for BinarySearch is a 2-tree that is full at every
level but the deepest, or equivalently, it is full at the second-deepest level, by the strong
form of induction on the input list size n.
Basis step: n = 2. Second-deepest level is Level 0 containing 1 = 20 node, i.e., the root.
4.13 a) Suppose T is any k-ary tree. Then we have
1)1)()1((log)( −+− TnkTd k
.
b) Suppose T is any k-ary tree. Then we have
I(T)=(L(T) – 1)/(k – 1).
Equivalently, we have
Algorithms: Sequential, Parallel and Distributed 4-7
obtained from T by deleting these children. By induction
4.14 Basis step:
3/4
112
4
2
1
12 1
=
+
=
12
4
2
+
n
n
nn
.
1)1(2
4
22
4
12
4
)1(
)12(2
2
)1(
)12(2
!!)1)(1(
)!2)(12)(22(
)!1()!1(
)!22(
1
)1(2
11
++
+
=
++
+
+
+
=
++
++
=
++
+
=
+
+
++
nn
nn
n
n
n
n
n
nnnn
nnn
nn
n
n
n
nn
n
This completes the induction step.
4.15 Let Ti be the set of all binary tree on n nodes having i nodes in the left subtree,
=
ii
0||
Since all the tree in Ti are constructed by all combinations of choosing a binary tree of size i as
the left subtree and a binary tree of size n – i + 1 as the right subtree, we have
4.16 We suppose that the tree is maintained using the parent array representation
Parent[0:n – 1 ] as illustrated in Figure 4.10a. The following pseudocode converts it to a
child-sibling representation, where the record TreeNode is as described on p. 128.
procedure ParentToChildSibling(Parent[0:n – 1],Root)
Input: Parent[0:n – 1] (parent array representation of a binary tree T)
if Parent[i] = 0 then // i is root
Root ← TreeNodes[i]
else
if TreeNodes[Parent[i]] → LeftMostChild = null then
TreeNodes[Parent[i]] → LeftMostChild ← TreeNodes[i]
4.17 a)
procedure TreePreorder(Root) recursive
Input: Root (pointer to the root of a tree T)
Output: each left and right child of T are swapped
Algorithms: Sequential, Parallel and Distributed 4-9
b) In the case when the into tree to TreePreorder is applied to a binary tree, i.e., Root points to
c) Observing that the left child of a node in
T
corresponds to the leftmost child of the same
4.18 a) Suppose Substr(S,i,j) is a function that returns the substring of length j of S beginning at
the ith character. Also, suppose Index(S1,S2) returns the position of the first character of S1
where the string S2 occurs, or zero if there is no such occurrence. Then the following
recursive procedure returns a pointer to the binary tree whose preorder and inorder traversals
are given by the strings S1 and S2, respectively. If no such tree exists, it returns null.
b) The two 2-node binary trees having nodes a,b, with a as the root, both have preorder
page 127. Then the following recursive procedure swaps the left and right child of each
node:
procedure Swap(Root) recursive
Input: Root (pointer to a binary tree T)
4.20 a) In the case of unary operations we will store the only child as the left child.
procedure ExpressionTree(S[low:high],Root) recursive
Input: S[low:high] (substring of a sting S from low to high representing an expression)
Output: Root (points to the binary expression tree for S[low:high])
AllocateBinaryTreeNode(Root)
ExpressionTree(S[low + 1: i], Root→LeftChild)
ExpressionTree(S[i + 2: high – 1], Root→RightChild)
endif
endif
end ExpressionTree
4.21
function InOrderSucc(P)
Input: P (pointer to a node in a binary tree with parent pointers)
Output: pointer to the inorder successor of node pointed to by P
4.22
procedure InOrder3(Root)
Input: Root (pointer to the root node of a tree T) //T is assumed nonempty
Output: the inorder traversal of T
stack S //initialize empty stack
4.23 We assume that the nodes of the threaded binary tree are records of the form described in
the previous exercise. Then the following pseudocode generates an inorder traversal.
procedure InOrder4(Root)
Input: Root (pointer to root of an inorder-threaded nonempty binary tree T)
Output: The inorder traversal of T
4.27 a) Pseudocode for a nonrecursive version for a preorder traversal results from a simple
modification of InOrder3 given in the solution to Exercise 4.22. The modification consists in
b) Pseudocode for a (structured) nonrecursive version for a postorder traversal
is not so straightforward as for the other two traversals since, for example, it is not tail
recursion. The canonical translation resulting from removing the recursive calls yields the
following (spaghetti) pseudocode.