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[0]**. - 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]**.

- It’s left child is stored in

A tree of height h will require an array of maximum size** 2 ^{h}-1**. A tree is empty if

`TREE[0] = 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.

## Applications of Binary Tree

- For rapid and easy access to data.
- Routing algorithms.
- To implement heap data structure.
- Syntax tree, Binary Search Tree, Hash Trees, Treap, T-tree, etc.