A binary tree is a special kind of tree and important in computer science. There are plenty of real world application of binary trees. The scope of this lesson is limited to the learning the concepts of a binary tree.

### Informal definition

A tree is called a binary tree if it has the following properties.

- It is an empty tree with no nodes.
- The tree has a root node, left sub-tree and right sub-tree.
- The sub-trees are binary tree themselves.

### Strictly Binary Tree

Suppose there is a binary tree with** right sub-tree** and **left sub-tree**. The sub-trees are in turn non-empty, then such a binary tree is called a** strictly binary tree**.

In the above figure, one is a strictly binary tree and the second tree is not a strictly binary tree, but it is certainly a binary tree and satisfy all the properties of a binary tree.

### Complete Binary Tree

A complete binary tree has a level L and all its leaf nodes are available at level L. At each level the complete binary tree contains 2^{L}nodes.

Let us show this with an example,

The root is at level 0, therefore, L = 0 and 2^L = 2^0 = 1.

### Conversion of a Binary forest into a Binary Tree

- If a node has left child, then if comes immediately below the node.
- If a node has another node in the save level, then it becomes the right child of the node.
- If a node has right child then, ignore it.

### Total Number of Edges

2 ( N_{L} – 1) where N_{L }is total number of leaf nodes. For example, see the tree below.

In the above diagram, we have N_{L} = 8 .

Therefore,

**= 2( N _{L} – 1) **

**= 2 ( 8 – 1)**

**= 2 (7)**

**= 14 edges.**

### Height of a Binary Tree

The maximum level of any node of the binary tree is called the height of a binary tree.

For example, see the figure below.

In the above tree figure, the maximum level of the tree is 4,

Therefore, the height of the tree is Height(T) = 4.

### Bibliography

R.G.Dromey. 2008. *How to Solve it by Computer.* Pearson Education India.

Robert Kruse, Cl Tondo. n.d. *Data Structures and Program Design in C.* Pearson Education India.

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. 2009. *Introduction to Algorithms.* MIT Press.