I Problem DS-04-06 A full node is a node with two children.

Prove that the number

of full nodes plus one is equal to the number of leaves in a nonempty binary tree.
Proof. For any given binary tree T , let F (T ) be the number of full nodes in T , L(T ) the
number of leaves in T , and H(T ) the number of half nodes (i.e., nodes with one child) in
T . We will show that L(T ) = F (T ) + 1 for any binary tree T with N nodes.

We first give a proof by induction on N . For N = 1, it is obvious that the tree

contains a single leaf and without full nodes. Thus the statement is true. We suppose
that L(T ) = F (T ) + 1 is true for any binary tree T with N ≥ 1 nodes. We now consider a
tree T with N + 1 nodes and let x be a leaf in T . Let T − x denote the tree obtained from
T by removing x from it. Also, we let p(x) denote the parent of x in T . From induction
hypothesis, we have L(T −x) = F (T −x)+1. We consider the following two cases. If p(x)
is a half node in T (i.e., p(x) contains x as the only child in T ), then L(T ) = L(T − x)
and F (T ) = F (T − x). This implies L(T ) = F (T ) + 1. On the other hand, if p(x) is a
full node in T , then L(T ) = L(T − x) + 1 and F (T ) = F (T − x) + 1. This again implies
L(T ) = F (T ) + 1. 

Proof. The following is another proof without using induction. It is clear that for any
binary tree T with N nodes, N = F (T ) + H(T ) + L(T ). Since every tree T with N nodes
contains N − 1 branches and 2 · F (T ) + 1 · H(T ) + 0 · L(T ) = N − 1. Subtracting yields
L(T ) − F (T ) = 1. 

1
I Problem DS-04-09

(a) Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an intially empty binary search
tree.

(b) Show the result of deleting the root.

Solution.

(a) (b)
3 4

1 4 1 6

2 6 2 5 9

5
9 7

1
I Problem DS-04-16 Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an intially
empty AVL tree.
Solution.

2 6

1 3 5 9

1
I Problem DS-04-17 Keys 1, 2, . . . , 2k − 1 are inserted in order into an initially empty
AVL tree. Prove that the resulting tree is perfectly balanced.
Proof. We first verify by hand that the claim is true for 1 ≤ k ≤ 3 as follows.

k=1 Insert 1 = 21 − 1 1 perfectly balanced

Insert 2 1

k=2 Insert 3 = 22 − 1 1
2
2 perfectly balanced
1 3
3

Insert 4 2

1 3

Insert 5 2 2

1 3 1 4

4 3 5

Insert 6 2
4
1 4
2 5
3 5
1 3 6
6

k=3 Insert 7 = 23 − 1 4
4
2 5
2 6
1 3 6
1 3 5 7
7
perfectly balanced

We prove the exercise by induction and suppose it is true for k = 1, 2, 3, . . . , H. Then

after the first 2H −1 insertion, 2H−1 is at the root, and the right subtree is a balanced tree
containing 2H−1 +1 through 2H −1. Each of the next 2H−1 insertions (namely, 2H through
2H + 2H−1 − 1) insert a new maximum and get placed in the right subtree, eventually
forming a perfectly balanced right subtree of height H − 1. This follows by the induction
hypothesis because the right subtree may be viewed as being formed from the successive
insertion of 2H−1 + 1 through 2H + 2H−1 − 1. The next insertion forces an imbalance at

1
the root, and thus a single rotation. It is easy to check that this brings 2H to the root
and creates a perfectly balance left subtree of height H − 1. The new key is attached to a
perfectly balanced right subtree of height H − 2 as the last node in the right path. Thus
the right subtree is exactly as if the nodes 2H + 1 through 2H + 2H−1 were inserted in
order. By the inductive hypothesis, the subsequent successive insertion of 2H + 2H−1 + 1
through 2H+1 − 1 will create a perfectly balanced right subtree of height H − 1. Thus
after the last insertion, both the left and the right subtrees are perfectly balanced, and
of the same height, so the entire tree of 2H+1 − 1 nodes is perfectly balanced (and has
height H). 

2
I Problem DS-04-22 Write the functions to perform the double rotation without the
inefficiency of doing two single rotations.
Solution.

Position DoubleRotationWithLeft( Position K3 )

{
Position K1, K2;

K1 = k3->Left;
K2 = K1->Right;
K1->Right = K2->Left;
K3->Left = K2->Right;
K2->Left = K1;
K2->Right = K3;

/* Update height */
K1->Height = Max( Height(K1->Left), Height(K1->Right) ) + 1;
K3->Height = Max( Height(K3->Left), Height(K3->Right) ) + 1;
K2->Height = Max( K1->Height, k3->Height ) + 1;

return K2;
}

Position DoubleRotationWithRight( Position K1 )

{
Position K2, K3;

K3 = k1->Right;
K2 = K3->Left;
K1->Right = K2->Left;
K3->Left = K2->Right;
K2->Left = K1;
K2->Right = K3;

/* Update height */
K1->Height = Max( Height(K1->Left), Height(K1->Right) ) + 1;
K3->Height = Max( Height(K3->Left), Height(K3->Right) ) + 1;
K2->Height = Max( K1->Height, k3->Height ) + 1;

return K2;
}

1
I Problem DS-04-23 Show the result of accessing the keys 3, 9, 1, 5 in order in the
splay tree shown below.

10

4 11

2 6 12

1 3 5 8 13

7 9

Solution.

After accessing 3 After accessing 9

3
9
2 10 3 10

1 4 11 2 4 11

6 12 1 8 12

5 8 6 13
13
5 7
7 9

After accessing 1
After accessing 5
1
5
9
1 9
2 10
2 6 10
3 11
4 8 11
12
4
13 3 12
7
8

6 13

5 7

1
I Problem DS-04-24 Show the result of deleting the element with key 6 in the resulting
splay tree for the previous exercise.
Solution.

After deleting 6

1 9

2 8 10

11
4 7

3 12

13

2
I Problem DS-04-25 Nodes 1 through N = 1024 form a splay tree of left children.

(a) What is the internal path length of the the tree (exactly)?

(b) Calculate the internal path length after each of F ind(1), F ind(2), F ind(3), F ind(4),
F ind(5), F ind(6).

(c) If the sequence of successive F inds is continued, when is the internal path length
minimized?

Solution. (a) The internal path length is defined to be the sum of the depths of all nodes
in a tree (See page 108 in textbook for definition). Let d(i) be the depth of node i. From
the structure of the given splay tree, it is easy to see that d(i) = 1024 − i. Thus, the
internal path length is
1024 1024 1023
X X X 1023 · 1024
d(i) = (1024 − i) i= = 523776.
i=1 i=1 i=0
2

1
I Problem DS-04-28 Write efficient functions that take only a pointer to the root of
a binary tree, T , and compute:

(a) The number of nodes in T .

(b) The number of leaves in T .

(c) The number of full nodes in T .

What is the running time of your routines?

Solution. All the following functions use the type SearchTree to represent the pointer
to the root, which is the same as TreeNode *, in Figure 4.16. As a result, all these
functions take O(N ) time, where N is the number of nodes in the tree T .

(a) Compute tree nodes:

int ComputeTreeNodes( SearchTree T )

{
if ( T == NULL ) return 0;
return 1+ComputeTreeNodes(T->Left)+ComputeTreeNodes(T->Right);
}

(b) Compute tree leaves:

int ComputeTreeLeaves( SearchTree T )

{
if ( T == NULL )
return 0;
else if ( T->Left == NULL && T->Right == NULL )
return 1;
return ComputeTreeLeaves(T->Left)+ComputeTreeLeaves(T->Right);
}

(b) Compute full nodes:

int ComputeTreeLeaves( SearchTree T )

{
int full = 0;
if ( T == NULL )
return 0;
else if ( T->Left != NULL && T->Right != NULL )
full = 1;
return full+ComputeTreeLeaves(T->Left)+ComputeTreeLeaves(T->Right);
}

1
I Problem DS-04-29 Write a function to generate an N -node random binary search
tree with distinct keys 1 through N . What is the running time of your routine?
Solution. We assume the existence of a function RandInt(Lower,Upper), which gener-
ates a uniform random integer in the appropriate closed interval in a constant time. The
following function RandomBinaySearchTree is clearly a linear time routine, and it will
return NULL if N is not positive, or if N is so large that memory is exhausted.

SearchTree MakeRandomTree( int Lower, int Upper )

{
SearchTree T;
int RandomValue;

T = NULL;
if ( Lower <=Upper )
{
T = malloc( sizeof( sturct TreeNode ) );
if ( T != NULL )
{
T->Element = RandomValue = RandInt( Lower, upper );
T->Left = MakeRandomTree( Lower, RandomValue-1 );
T->Right = MakeRandomTree( RandomValue+1, Upper );
}
else
FatalError( "Out of space!" );
}
return T;
}

SearchTree RandomBinaySearchTree( int N )

{
return MakeRandomTree( 1, N );
}

1
I Problem DS-04-30 Write a function to generate the AVL tree of height H with
fewest nodes. What is the running time of your function?
Solution.

AvlTree GenAVLTree( int height, int *lastnode )

{
AvlTree T;

if ( height < 0 )
return NULL;
else
{
T = (AVlTree) malloc( sizeof(struct AvlNode));
if ( T == NULL)
FatalError( "Out of space!!!" );
else
{
T->Left = GenAVLTree( height - 1, lastnode );
T->Element = ++*lastnode;
T->Height = height;
T->Right = GenAVLTree( height - 2, lastnode );
return T;
}
}
}
AvlTree GenerateAVLTreeWithFewestNodes(int H)
{
int LastNodeAssigned = 0;
return GenAVLTree( H, &LastNodeAssigned );
}

The precise expression for the minimum number of nodes in an AVL tree of height H
is the following:

N ode(H) = N ode(H − 1) + N ode(H − 2) + 1 H≥2
N ode(0) = 1, N ode(1) = 2

Thus, the minimum number of nodes in an AVL tree with height H is one less than the
Fibonacci number FH+2 , as shown in below.

H 0 1 2 3 4 5 6 7 8 9 ···
FH 1 1 2 3 5 8 13 21 34 55 ···
N ode(H) 1 2 4 7 12 20 33 54 88 143 ···

This shows that the function GenerateAVLTreeWithFewestNodes(H)

h √ H+1  √ H+1 i can be bounded in
1 1+ 5 1− 5
O(FH+2 ) time, where FH = √5 2
− 2
.

1
I Problem DS-04-32 Write a function that takes as input a binary search tree, T ,
and two keys k1 and k2 , which are ordered so that k1 ≤ k2 , and prints all element X
in the tree such that k1 ≤ Key(X) ≤ k2 . Do not assume any information about the
type of keys except that they can be ordered (consistently). Your program should run in
O(K + log N ) average time, where K is the number of keys printed. Bound the running
time of your algorithm.

Solution. We implement this procedure using a routine similar to the inorder traversal
of a tree.

void PrintElementRange( ElementType K1, ElementType K2, SearchTree T )

{
if ( T != NULL )
{
if ( K1 <= T->Element)
PrintElementRange( K1, K2, T->Left );
if ( K1 <= T->Element && T->Element <= K2 )
PrintLine( T->Element );
if ( T->Element <= k2 )
PrintElementRange( K1, K2, T->Right );
}
}

The time is O(K) to perform the inorder traversal, if a significant number of nodes
are found, and also proportional to the depth of the tree, if we get to some leaves (for
instance, if no nodes are found). Since the average depth is O(log N ), this gives an
O(K + log N ) average bound.

1
I Problem DS-04-35 Write a routine to list out the nodes of a binary tree in level-
order. List the root, then nodes at depth 1, followed by nodes at depth 2, and so on. You
must do this in linear time. Prove your time bound.
Solution. Put the root on an empty queue. Then repeatedly dequeue a node and en-
queue its left child and right child (if any) until the queue is empty. This is an O(N ) time
routine because each queue operation requires constant time and there are N Enqueue
and N FrontAndEnqueue operations. In the following procedure, we suppose that a
pointer T has pointed to the root of a tree.

void LevelOrderTraversal( SearchTree T )

{
Queue Q;
Position temp = T;

Enqueue( T, Q );
while ( !isEmpty( Q ) )
{
temp = FrontAndDequeue( Q );
PrintLine( temp->Element );
if ( temp->Left != NULL )
Enqueue( temp->Left, Q );
if ( temp->Right != NULL )
Enqueue( temp->Right, Q );
}
}

1
I Problem DS-04-36

(a) Show the result of inserting the following keys into an initially empty 2-3 tree: 3, 1,
4, 5, 9, 2, 6, 8, 7, 0

(b) show the result of deleting 0 and then 9 from the 2-3 tree created in part (a).

Solution.

(a)

6:-

2:4 8:-

0,1 2,3 4,5 6,7 8,9

(b)
6:-

2:4 8:-

1 2,3 4,5 6,7 8

1
I Problem DS-04-41 Two binary trees are similar if they are both empty or both
nonempty and have similar left and right subtrees. Write a function to decide whether
two binary trees are similar. What is the running time of your program?
Solution. The function shown below is clearly a linear time routine because in the worst
case it does a traversal on both T1 and T2 .

int Similar( BinaryTree T1, BinaryTree T2 )

{
if ( T1 == NULL || T2 == NULL )
return ( T1 == NULL && T2 == NULL );
else
return ( Similar( T1->Left, T2->Left ) &&
Similar( T1->Right, T2->Right) );
}