c111 - page 1 of 1

Chapter 11

Binary Trees

Sangwook Kim, Kyungpook National University, Korea (swkim@cs.knu.ac.kr)

Chapter Outline:

11.1. Binary Tree

11.1.1. Definition and Properties

11.1.2. Traversal of Binary Tree

11.1.3. Implementation of Binary Trees

11.2. Binary Search Trees

11.2.1. Definition

11.2.2. Insertion into a Binary Search Tree

11.2.3. Deletion from a Binary Search Tree

11.2.4. Search of a Binary Search Tree

11.2.5. Implementation of a Binary Search Tree

11.3. An AVL Tree and Balancing Height

11.3.1. Definition

11.3.2. Insertion into an AVL Tree

11.3.3. Deletion from an AVL Tree

11.3.4 Implementation of an AVL Tree

Exercises

Chapter 11 Binary Trees

We can represent any tree as a binary tree. Binary trees are an important type of tree structure.

In this chapter, we study binary tree as data structure using the linked list for their

implementation. Binary tree is valuable data structure for a range of applications in computer

science.

11.1. Binary Tree

In this section, we study the definition of the binary tree. The binary tree can illustrate the

behavior of the some algorithms as sorting and searching. Especially, we have used comparison

trees showing the comparison keys in searching.

11.1.1. Definition and Properties

A binary tree is a different type from a tree. Binary trees have characteristics that any node can

have at most two branches. Thus, we distinguish between the subtree on the left and the subtree

on the right for binary trees. Also a binary tree may have zero nodes.

Definition: A binary tree is either empty, or it consists of a root and two disjoint binary trees

called the left subtree and the right subtree.¦

Before we consider general characteristics of binary tree, we can construct small binary trees by

recursion.

1) If the number of node is zero, there is an empty binary tree.

2) If the number of node is one, there is only binary tree with root node that both the left and the

right subtrees are empty.

3) If the number of node is two, one node on the tree is the root and another node is in a subtree.

In this case, one of the left and the right subtree must be empty, and the other subtrees have

exactly one node. Thus we have two different binary trees with two nodes.

Fig. 11.1. A binary tree with one node and two different binary trees with two nodes

In the binary tree, since the left and right are important, binary trees with two nodes in Fig.

11.1 are different from each other.

4) If the number of node is three, one of three nodes is the root and other two nodes will be

one of the followings.

(1)

Two node in left subtrees and empty in right subtree: In this case, we have two binary

trees as Fig. 11.2, since there are two binary trees with two nodes and only one empty

tree.

Fig. 11.2. Binary trees with two nodes in left subtrees

(2)

Empty in left subtree and two nodes in right subtree: In this case, we have two more

binary trees ad Fig. 11.3.

Fig. 11.3. Binary trees with two nodes in right subtrees

(3)

One node in left subtrees and one node in right subtree: In this case, we have one

binary tree as Fog. 11.4, since the left and right subtree both have one node, and there

is only one binary tree with one node.

Fig. 11.4. Binary trees with one node in left subtrees and one node in right subtree

We knew already that when there are three nodes, we construct five binary trees with three

nodes.

And now, if there are many nodes, how many binary trees can we construct? Let n be the

number of nodes and BT(n) be the number of binary trees to be constructed. From above

observation, BT(1) = 1, BT(2) = 2 and BT(3) = 5.

If n =4, BT(4) is calculated as follows.

After one node is selected as root node, there are four cases according to the number of nodes in

the left (and right) subtree of the root as follows.

In case 1, the number of binary trees with three nodes in left subtree is five and the number of

binary trees with zero node in right subtree is one as we know. In case 2, the number of binary

trees with two nodes in left subtree is two and the number of binary trees with one node in right

subtree is one. The case 3 and case 4 are same. Thus we can obtain the followings.

In case 1, BT(3) ×

BT(0) = 5 x 1 = 5

In case 2, BT(2) ×

BT(1) = 2 x 1 = 2

In case 3, BT(1) ×

BT(2) = 1 x 2 = 2

In case 4, BT(0) ×

BT(3) = 1 x 5 = 5

Thus, BT(4) = 5 + 2 + 2 + 5 = 14. Also BT(5) = 42, and BT(6) = 132. Generally, the number of

binary trees with n nodes is

BT(n) = ? ( BT(i-1) × BT(n-i) ), n =

1 and BT(0) = 1.

i=1

For an example, Fig. 11.5 shows fourteen binary trees with four nodes.

Fig. 11.5. Fourteen binary trees with 4 nodes

We can observe some characteristics from construction of binary trees for n nodes. There are n-1

nodes, n-2 nodes, …, 1, and 0 node in left(and right) subtree. These numbers of nodes determine

the depth d of binary tree.

Suppose that the root of a binary tree has level 0. Since the root is only node on level l = 0, the

maximum number of nodes on level l = 0 is 2

= 2

= 1. Thus, the maximum number of nodes on

level l is computed as follows.

For level l = 0, 2

= 1.

For level l = 1, 2¹ = 2.

For level l = 2, 2² = 4.

………

For level l = i, 2

The maximum number of nodes on level i is two times the maximum number of nodes on level i

– 1 (or 2

). Finally, the maximum number of nodes on the level l of a binary tree is 2

nodes, l =

Also, if we use the maximum number of nodes on the level l (l = 0)of a binary tree, we can know

the maximum number of nodes in a binary tree of depth d. That is as follows.

Maximum number of nodes in a binary tree of depth d

d-1

= ? ( maximum number of nodes on level l )

l=0

d-1

= ?

= 2

– 1

l=0

where d = 1.

Definition: If a binary tree of depth d has 2

– 1 nodes, it is a full binary tree of depth d, d=1.¦

The number of 2

– 1 nodes is the maximum number of nodes in a binary tree of depth d. For

the full binary tree starting with the root on the level 0 in Fig. 11.6, the depth is 4 and the

number of maximum nodes is 15.

Fig. 11.6. Full binary tree of dept 4 and 15 nodes

Definition: A binary tree with n nodes and depth d is complete iff its nodes have

correspondence to the nodes numbered from 1 to n in the full binary tree of depth d.¦

This binary tree can apply to various fields as VLSI design, computer network structure and

algorithm design in computer science. Fig. 11.7 shows an example for VLSI circuit design using a

binary tree. Some applications of a binary tree will be shown in this chapter.

Fig. 11.7. An example of VLSI circuit design using full binary tree with 15 nodes

11.1.2. Traversal of Binary Tree

There are many operations to be performed on a binary tree. One of their operations is the

traversing

binary tree. This traversing tree is important and there are many applications in

computer science. Traversing tree is to visit each node in the tree exactly once. We can obtain an

ordered sequence of nodes for a tree as result by traversing a tree. However, we obtain some

different order of nodes according to the way traversing a binary tree. At a given a binary tree,

we can visit a node itself, traverse its left subtree, and traverse its right subtree.

In traversal order, it is important to decide the position of visiting node itself in the binary tree.

The position is one of followings.

before traversing either subtrees

between the subtrees

after traversing both subtrees

Thus we can obtain six traversing as shown in Fig. 11.8. If we name visiting a node V, traversing

the left subtree L, and traversing the right subtree R, we can rewrite six traversing order as

follows.

V L R L V R L R V V R L R V L R L V

As these traversing, we can visit all the nodes of the binary tree

in turn. Since traversing left

subtree and traversing right subtree is symmetric, we can reduce these six to three by traversing

left subtree before right subtree as V L R, L V R and L R V only.

According to the position of visited node, we call these preorder, inorder and postorder,

respectively. These are named according to the turn at which the given node is visited.

•

Preorder traversal (VLR): the node is visited before the subtrees.

•

Inorder traversal (LVR): the node is visited between the subtrees.

•

Postorder (LRV): the node is visited after both of the subtrees.

Fig. 11.8. Six examples of traversing of binary tree

As an example, consider the binary tree of Fig. 11.9 to represent arithmetic expression X + (C * D

/ B – 3 ^ 4). This binary tree contains an arithmetic expression with some operators and

operands. These binary operators are add (+), multiply (*), minus (-), divide (/) and power (^),

and operands are 3, 4, B, C, D and X. For each node that contains an operator, its left subtree

gives the left operand, and its right subtree gives the right operand.

Fig. 11.9. An binary tree for X + (C * D / B – 3 ^ 4)

Let us traverse given binary tree.

In the preorder traversal, we visit the root node, labeled + first. Then we traverse the left subtree.

We visit node X, since node X does not have both left and right subtree in the given binary tree.

And we move the traversal to the right subtree of the root. In the right subtree, we can find some

nodes labeled -, /, ^, *, B, 3, 4, C, and D. At this point, we must traverse this subtree using the

preorder method. We visit the root, labeled -, of this subtree, and then traverse the left subtree

of node -. Again, we visit root node /, and then traverse the left subtree of node /. Node * is

visited. Continuously, we traverse the left subtree of node *, then we visit node C. Since both left

and right subtrees of node C are empty, we cannot traverse the both subtrees of node C. Thus we

visit node D in the right subtree of node *. After visiting node D, node B is visited. Since we have

traversed the left subtree of node -, we traverse the right subtree of node -. Node ^ is visited, and

then node 3 in left subtree and node 4 in right subtree are visited. Thus we visit the nodes in the

order +, X, -, /, *, C, D, B, ^, 3 and 4 by the preorder traversal of the binary tree.

In the inorder traversal, we traverse the left subtree of the root node +. We visit the node labeled

X first, and then visit the root node +. Next we move the traversal to the right subtree of node +.

In the right subtree of node +, we must traverse it using inorder method. We must traverse the

left subtree of node - before visiting node -. Its root of left subtree of node - is node /, and has

the left subtree containing nodes *, C, D and B. Since node * is root, after visiting node C, we

visit node * and node D in order. Also since node / is root of nodes *, C and D, we visit node /

and node B in order. Since the left subtree of node – has visited, node – is visited. At this point,

we move the traversal to the right subtree of node -. Since the root of the right subtree of node –

is node ^, we must visit node ^ after visiting node 3, and visit node 4 in order. Thus we visit the

nodes in the order X, +, C, *, D, /, B, -, 3, ^, and 4 by the inorder traversal of the binary tree.

In the postorder traversal, before visiting node itself, we traverse both the left subtree and right

subtrees of each node first. By this postorder traversal, the root of a binary tree is always visited

lastly. We visit the node labeled X first. Then we move the traversal to the right subtree of node

+. In the right subtree of node +, we must traverse it using postorder method. We must traverse

the left subtree of node - before visiting right subtree of node -. Its root of left subtree of node -

is node /, and has the left subtree containing nodes *, C, D and B. Before visiting node *, we

must visit node C and node D in order. Also after node B is visited, node / is visited. At this point,

we move the traversal to the right subtree of node -. Since the root of the right subtree of node –

is node ^, we must visit node 3 and node 4 in order first. After visiting nodes 3 and 4, we visit

node ^, and then we must visit node – and + in order. Thus we visit the nodes in the order X, C,

D, *, B, /, 3, 4, ^, - and + by the inorder traversal of the binary tree.

Finally, we obtain the traversal result on the binary tree in Fig. 11.9 as follow.

• Preorder: + X - / * C D B ^ 3 4

• Inorder: X + C * D / B - 3 ^ 4

• Postorder: X C D * B / 3 4 ^ - +

The arithmetic expression containing unary or binary operator can be represented by a binary

tree. A binary tree traversal can be applied to the compiler. When compiler recognizes an

arithmetic expression, it represents traversal order for arithmetic expression and generates

object codes according to the evaluation. As you see, the traversing result decides the operator

precedence for arithmetic expression according to the evaluation direction. Now we define the

expression tree.

Definition:

expression tree is the binary tree, which is consists of simple operands and

operators of an expression. The leaves of a binary tree contain simple operands and the interior

nodes contain the operators. For each binary operator, the left subtree contains all the simple

operands and operators in the left operand of the given operator, and the right subtree contains

everything in the right operand. For a unary operator, one of the two subtrees will be empty.¦

For an example of code generation of the expression tree in Fig. 11.9, the compiler to use one

address instruction format can generates following object code (pseudo code) based on

evaluation of postorder traversal.

…

load X

load C

load D

mul

load B

div

load 3

load 4

pwr

minus

plus

…

Fig. 11.10 shows the evaluation sequence of example object code to be generated by compiler.

Also the binary tree is very useful and efficient for searching and sorting.

Fig. 11.10. An evaluation of expression tree for X + (C * D / B – 3 ^ 4)

11.1.3. Implementation of Binary Trees

We study the implementation of a binary tree to perform what we have studied before including

data structure for a binary tree, traversal functions and main function. Also, we make function

for an example of the code generation and evaluation of a binary tree in Fig. 11.9.

We must represent mathematical definition as an abstract data type. If binary tree is specified as

an abstract data type, we manipulate some operations to be performed on this binary tree. Also

we must add reference to the way in which binary trees will be implemented in memory. Thus

we use linked representation for easy use, and also reference to keys or the way in which they

are ordered.

Linked implementation uses storage to be formed two fields of data and pointer. Since a binary

tree is constructed in linked structures, all the nodes are linked in storage dynamically. In order

to find the tree in storage, we need a special pointer. The name for this pointer is root, since this

pointer points to the root of the tree. Using this pointer, we recognize easily an empty binary

tree as if root = null. We assign its root pointer to null to create a new empty binary tree. Fig.

11.11 is the linked binary tree of Fig. 11.9. As you see, the difference between them is that linked

binary tree has null links explicitly.

Fig. 11.11. A linked binary tree

1) Declaration of data structure for a binary tree

For linked implementation of the binary tree, we construct the its data structure and each node

in a binary tree.

In a binary tree, each node has three fields; left subtree, right subtree and data. As with linked

lists, we use two types to define a binary tree in syntax of C programming language. Two struct

are as follows.

typedef struct treenode TreeNode;

typedef struct treenode{

TreeNode *LeftSubTree;

TreeEntry Entry;

TreeNode *RightSubTree;

} TreeNode;

In this declaration, *LeftSubTree is the pointer for left subtree, *RightSubTree is the pointer

for right subtree, and Entry is data for binary tree. The type TreeEnrty depends on the

application.

In order to use this linked binary tree practically, we must initialize the binary tree. The

initialization is to create a binary tree and to check if the tree is empty or not. In creating a

binary tree, we make a new empty binary tree to which root points. Also we obtain value true or

false according as the tree is empty or not. Two functions, CreateTree and TreeEmpty, are built

easily.

2) Traversal function

In order to make functions to traverse a linked binary tree for three traversal methods, preorder,

inorder and postorder, we have studied. In each of the three methods, we use recursion. It

makes easy. We assume that we have root to be a pointer to the root of the tree

and another

function Visit that visit a node according to request

for each node. Three functions, Preorder,

Inorder and Postorder, are as follows. The Preorder function visits each node of the tree in

preorder. The result is preorder sequence of nodes that have been performed on every entry in

the binary tree. There are some related functions for preorder in exercise and solution.

/* Visiting each node of the binary tree in preorder sequence. */

void Preorder(TreeNode *CurrentNode)

{

if (CurrentNode)

{

Visit(CurrentNode->Entry);

Preorder(CurrentNode->LeftSubTree);

Preorder(CurrentNode->RightSubTree);

}

The Inorder function visits each node of the binary tree in inorder. The result is inorder

sequences of nodes that have been performed on every entry in the binary tree.

/* Visiting each node of the binary tree in inorder sequence.

void Inorder(TreeNode *CurrentNode)

{

if (CurrentNode)

{

Inorder(CurrentNode->LeftSubTree);

Visit(CurrentNode->Entry);

Inorder(CurrentNode->RightSubTree);

}

The Postorder function visits each node of the tree in postorder. The result is postorder

sequences of nodes that have been performed on every entry in the binary tree.

/* Visiting each node of the binary tree in postorder sequence.

void Postorder(TreeNode *CurrentNode)

{

if ( CurrentNode )

{

Postorder(CurrentNode->LeftSubTree);

Postorder(CurrentNode->RightSubTree);

Visit(CurrentNode->Entry);

}

3) Evaluation function for an expression tree

This function evaluates the expression by making a left to right scan, stacking operand, and

evaluating operators popping proper operands and then placing the result into the stack. The

following is evaluation function.

void Evaluation(TreeNode *CurrentNode)

{

if (CurrentNode)

{

Evaluation(CurrentNode->LeftSubTree);

Evaluation(CurrentNode->RightSubTree);

switch(CurrentNode->Entry)

{

case

each operator x:

Pop the proper number of operands for operator x from stack;

Perform the operation x and store the result onto the stack;

default: push(CurrentNode->Entry);

}

4) Main function

In order to use some implementation functions for a linked binary tree, we call these functions

by main function.

In the main function, we assume that we have root to be a pointer to the root of the tree. The

function InitialTree()

makes a binary tree, and functions Preorder(root), Postorder(root), and

Inorder(root)

are used to traverse a binary tree. The function Evaluation(root)

is used for the

application of expression tree of an example.

void main( )

{

root = (TreeNode*) malloc(sizeof(treenode));

InitialTree();

Preorder(root);

Postorder(root);

Inorder(root);

Evaluation(root);

}