# Binary Trees

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.

### Graphs

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
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
}
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.