Binary Tree Representation in Data Structure

Binary Tree:

A binary tree is a finite set of elements that are either empty or it is partitioned into three disjoint subsets.
1. The first subset contains a single element that says the root of the tree.
2. The other two subsets are themselves binary trees say the left and the right sub-trees of the original tree.
3. Here every node can have at most two children.

Types of Binary Tree:

There are mainly three types of binary tree:
1. Complete Binary Tree
2. Full Binary Tree
3. Extended Binary Tree

Complete Binary Tree:

A binary tree is said to be complete if all its levels except possibly the last. It has the maximum number of possible nodes, and if all the nodes at the last level appear as far left as possible.

Full Binary Tree:

A binary tree said a full binary tree if it satisfies two conditions:
1. Each node has either zero or two children.
2. All the leaf nodes are at the same level.

Extended Binary Tree:

It is a binary tree where each node has either two or zero children. The node with zero children is called the external node and the node with two children is called an internal node. External nodes are represented by a square and internal nodes are represented by a circle.

Binary Tree Representation:

There are two general ways of Binary Tree Representation in memory.
1. Linked Representation
2. Sequential Representation

Linked Representation:

The most common and easiest way to represent a binary tree is using a linked list. Each node in a binary tree has three fields. One field is used to store the data value and the other two fields are used to store the address of the two children.

Sequential Representation:

This method is used to represent a binary tree in memory by an array. this method is useful for a complete binary tree and it is most efficient for a full binary tree.