  # Binary Tree

A Binary tree is a special tree where each node can have no more than two children. A non-empty binary tree consist of the following:

• A node called the root node.
• A left sub-tree.
• A right sub-tree.

Both the sub-trees are themselves binary trees.

## Types of Binary Trees

#### Complete Binary Tree

The tree T is said to be complete if,

• All it’s levels, except possibly the last, must be completely filled.
• All the leaf nodes must appear as far left as possible.

#### Full Binary Tree

A full binary tree is a special type of tree in which the leaf nodes will have zero children and other non-leaf nodes will have exactly 2 children.

## Representation of Binary Tree

Binary trees can be maintained in memory using either an array or a linked list.

#### Sequential representation of binary trees

The simplest technique for representing a binary tree is to store the elements using a one-dimensional array.

Suppose we are using a one-dimensional array TREE to store the elements of a tree. The rules for a sequential binary tree are as follows:

• The root of the tree will be stored in TREE.
• If an element is stored in TREE[K], then
• It’s left child is stored in TREE[2K + 1].
• It’s right child is stored in TREE[2K + 2].

A tree of height h will require an array of maximum size 2h-1. A tree is empty if `TREE = NULL`.

The following figure shows a binary tree and its corresponding sequential representation.

This method is inefficient unless the tree is (almost) full. Also, it is not possible to add a new node if the tree is already full.

#### Linked representation of binary trees

Every node in a linked representation of binary tree will contain three parts:

• The data element.
• A pointer to the left node.
• A pointer to the right node.

It can be represented by a structure.

```struct node {
struct node *left;
int data;
struct node *right;
};```

The root node is pointed by a pointer ROOT. The tree is empty if `ROOT = NULL`

The schematic diagram of the linked representation of the binary tree is shown below. 