*Definition:* A binary tree, T, is either empty or such that**1) T has a special node called the root node.****2) T has two sets of nodes, LT and RT, called the left subtree and right****subtree of T, respectively.****3) LT and RT are binary trees.**

A binary tree can be shown pictorially. Suppose that T is a binary tree with a root node

A. Let LA denote the left subtree of A and RA denote the right subtree of A. Now LA and

RA are binary trees. Suppose that B is the root node of LA and C is the root node of RA. B

is called the left child of A; C is called the right child of A. Furthermore, A is called the

parent of B and C

In the diagram of a binary tree, each node of the binary tree is represented as a circle and

the circle is labeled by the node. The root node of the binary tree is drawn at the top. The

left child of the root node (if any) is drawn below and to the left of the root node.

Similarly, the right child of the root node (if any) is drawn below and to the right of the

root node. Children are connected to the parent by an arrow from the parent to the child.

An arrow is usually called a directed edge or a directed branch (or simply a branch).

Because the root node, B, of LA is already drawn, we apply the same procedure to draw

the remaining parts of LA. RA is drawn similarly. If a node has no left child, for example,

when we draw an arrow from the node to the left child, we end the arrow with three

lines. That is, three lines at the end of an arrow indicate that the subtree is empty.

The root node of this binary

tree is A. The left subtree of the root node, which we denoted by LA, is the set LA ¼ {B,

D, E, G} and the right subtree of the root node, which we denote by RA, is the set RA ¼

{C, F, H}. The root node of the left subtree of A—that is, the root node of LA—is node

B. The root node of RA is C, and so on. Clearly, LA and RA are binary trees. Because

three lines at the end of an arrow mean that the subtree is empty, it follows that the left

subtree of D is empty.

Definition: The** level of a node** in a binary tree is the number of branches on the path

from the root to the node.

Clearly, the level of the root node of a binary tree is 0, and the level of the children of the

root node is 1.

Definition: The **height of a binary** tree is the number of nodes on the longest path

from the root to a leaf.

If the binary tree is empty, the height is 0. Suppose that the binary tree is nonempty. To

find the height of the binary tree, we first find the height of the left subtree and the height

of the right subtree. We then take the maximum of these two heights and add 1 to find

the height of the binary tree. To find the height of the left (right) subtree, we apply the

same procedure because the left (right) subtree is a binary tree. Therefore, the general

algorithm to find the height of a binary tree is as follows. Suppose height(p) denotes the

height of the binary tree with root p.**if (p is NULL)****height(p) = 0****else****height(p) = 1 + max(height(p->llink), height(p->rlink))****Clearly, this is a recursive algorithm. The following function implements this algorithm:****template <class elemType>****int height(binaryTreeNode<elemType> *p) const****{****if (p == NULL)****return 0;****else****return 1 + max(height(p->llink), height(p->rlink));****}**

The definition of the function height uses the function max to determine the larger of

two integers. The function max can be easily implemented.

Similarly, we can implement algorithms to find the number of nodes and number of leaves

in a binary tree.

**Binary Tree Traversal:**

The item insertion, deletion, and lookup operations require that the binary tree be

traversed. Thus, the most common operation performed on a binary tree is to traverse

the binary tree, or visit each node of the binary tree. As you can see from the diagram of a

binary tree, the traversal must start at the root node because there is a pointer to the root

node. For each node, we have two choices:**• Visit the node first.****• Visit the subtrees first.**

These choices lead to three different traversals of a binary tree—**Inorder, preorder, and****postorder.**

**Inorder Traversal**

In an inorder traversal, the binary tree is traversed as follows:

1. Traverse the left subtree.

2. Visit the node.

3. Traverse the right subtree.

**Preorder Traversal**

In a preorder traversal, the binary tree is traversed as follows:

1. Visit the node.

2. Traverse the left subtree.

3. Traverse the right subtree.

**Postorder Traversal**

In a postorder traversal, the binary tree is traversed as follows:

1. Traverse the left subtree.

2. Traverse the right subtree.

3. Visit the node

The listing of the nodes produced by the inorder traversal of a binary tree is called the**inorder sequence.**

The listing of the nodes produced by the preorder traversal of a

binary tree is called the **preorder sequence.**

The listing of the nodes produced by the

postorder traversal of a binary tree is called the **postorder sequence.**

**Definition: A binary search tree**, T, is either empty or the following is true:*i. T has a special node called the root node.**ii. T has two sets of nodes, LT and RT, called the left subtree and right**subtree of T, respectively.**iii. The key in the root node is larger than every key in the left subtree**and smaller than every key in the right subtree.**iv. LT and RT are binary search trees.*

The following operations are typically performed on a binary search tree:

• Search the binary search tree for a particular item.

• Insert an item in the binary search tree.

• Delete an item from the binary search tree.

• Find the height of the binary search tree.

• Find the number of nodes in the binary search tree.

• Find the number of leaves in the binary search tree.

• Traverse the binary search tree.

• Copy the binary search tree.