---

A binary tree is a tree which can be empty or can have a root R with at most 2 children. Each of these children then can be an empty tree or can again contain at most 2 children to form a binary tree. Following is an example of binary tree

Child node in a binary tree on the left is termed as left child node and node in the right is termed as the right child node.

A binary tree may also be defined as follows:

• A binary tree is either an empty tree
• Or a binary tree consists of a node called the root node, a left subtree and a right subtree, both of which will act as a binary tree once again

Application of Binary Tree

Binary trees are used to represent a nonlinear data structure. There are various forms of Binary trees. Binary trees play a vital role in a software application. One of the most important applications of the Binary tree is in the searching algorithm.

A general tree is defined as a nonempty finite set T of elements called nodes such that:

• The tree contains the root element
• The remaining elements of the tree form an ordered collection of zeros and more disjoint trees T₁, T₂, T₃, T₄ …. T_n which are called subtrees.

Types of Binary Tree

Full binary tree

Complete binary tree

Full binary tree

A full binary tree which is also called as proper binary tree or 2-tree is a tree in which all the node other than the leaves has exact two children.

Complete binary tree

A complete binary tree is a binary tree in which at every level, except possibly the last, has to be filled and all nodes are as far left as possible.

A binary tree is said to be a complete binary tree in data structure if it meets the following conditions

• All the levels except possibly the last level have the maximum number of possible nodes.
• All the nodes in the last level appear as far left as possible. That is, at the last level, there should not be any right successor of a parent not without a left successor

For example, the above-given figure of Binary Tree is not a Complete Binary Tree because the last level starts with no left children of D, even if D and  E were having 2 children each, still it could not be a Complete Binary Tree as because F doesn't have a left successor. Following is an example of a complete binary tree

• Extended binary tree

  A binary tree can be converted into an extended binary tree by adding new nodes to its leaf nodes and to the nodes that have only one child. These new nodes are added in such a way that all the nodes in the resultant tree have either zero or two children. It is also called 2 - tree.

• The threaded Binary tree

  The threaded Binary tree is the tree which is represented using pointers the empty subtrees are set to NULL, i.e. 'left' pointer of the node whose left child is empty subtree is normally set to NULL. These large numbers of pointer sets are used in different ways.

---